본문 바로가기

Medium174

[Leetcode] 452. Minimum Number of Arrows to Burst Balloons 문제 : https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/ points 배열을 start 기준 오름차순, start가 동일한 경우 end 기준으로 오름차순 정렬한다. points 배열을 앞에서부터 탐색하면서 중복되는 범위를 저장해둔다. (let, duplicate) duplicate 범위의 start가 end 보다 작아지는 경우 정답을 +1 하고 현재 탐색중인 points 배열 원소값으로 duplicate를 갱신한다. 문제의 예제 1번 예시. points = [[10,16],[2,8],[1,6],[7,12]] [1, 6] x -> [1, 6] 갱신 (정답 + 1) [2, 8] [2, 6] [7, 12] [7, 6] -> [.. 2022. 1. 13.
[Leetcode] 1041. Robot Bounded In Circle 문제 : https://leetcode.com/problems/robot-bounded-in-circle/ 로봇이 (0, 0) 위치에 북쪽 방향을 향하고 있다. 'G' : 1칸 앞으로. 'L' : 왼쪽으로 회전. 'R' : 오른쪽으로 회전. 로봇은 주어진 명령을 영원히 반복하며 이동한다고 할 때, 로봇이 특정 원을 벗어나지 않는지 구해라. 방향 회전은 L, R 90도씩만 움직이기 때문에 명령을 1번, 2번, 3번, 4번 수행 한 뒤 원점 (0, 0)으로 돌아올 수 있다면 특정 원을 벗어나지 않는 경우이고 4번 이내에 (0, 0)으로 돌아오지 않는다면 원을 벗어날 것이다. 시간복잡도는 O(N). 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetco.. 2022. 1. 11.
[leetcode] 1094. Car Pooling 문제 : https://leetcode.com/problems/car-pooling/ 총 좌석이 capacity인 차량이 있다. 차량엔 capacity 만큼의 탑승자만 태울 수 있다. 차량은 동쪽으로만 주행하며 (탑승자 수, from, to) 정보를 저장한 trip 배열이 주어진다. from에서 탑승자 수 만큼 차량에 태우고 to에 탑승자 수 만큼 차량에서 내린다. capacity를 넘지 않게 모든 trip 여행들을 탐색할 수 있으면 true 아니면 false를 반환하라. 부분합 배열을 만들어서 풀 수 있다. to의 최대값이 1000이므로 1000 크기의 passenger 배열을 만든다. trips 배열을 탐색하며 passenger[from] 에는 탑승자 수 만큼 더하고, passenger[to]에는 탑.. 2022. 1. 7.
[leetcode] 131. Palindrome Partitioning 문제 : https://leetcode.com/problems/palindrome-partitioning/ 문자열 s가 입력으로 주어지면 파티션의 모든 하위 문자열이 palidrome 이 되도록 하는 모든 경우를 구하라. 문자열을 앞뒤로 읽었을 때 같은 문자열인 경우 palidrome이라 한다. DP + backtracking 팰린드롬인지 구하는 함수. DP // dp[s][e] = str[s ~ e]가 palidrome인지 fun isPalidrome(str, s, e) { if(dp[s][e]가 없으면) dp[s][e] = str[s]와 str[e]가 같은 문자이며 isPalidrome(str, s+1, s-1) 인 경우 return dp[s][e]; } 팰린드롬 하위 문자열들을 만들어서 partit.. 2022. 1. 6.
[Leetcode] 56. Merge Intervals 문제 : https://leetcode.com/problems/merge-intervals/ 간격 start, end 를 저장한 interval 배열이 주어질 때, 겹치는 모든 간격을 병합하여 간격이 겹치지 않게 만든 뒤 간격 배열을 반환하라. intervals 배열을 start 오름차순으로 정렬한다. start, end 변수를 만들고 겹치는 간격을 만나면 end 변수를 갱신해간다. 정렬한 배열을 앞에서부터 탐색하며 종료 간격 end가 탐색하는 간격의 start보다 같거나 크다면 합쳐질 수 있는 경우이므로 end를 갱신한다. 만일 그렇지 않다면 start, end를 정답 배열에 추가한다. [[1,3],[2,6],[8,10],[15,18]] 예시 intervals[i] start end answer 배열 .. 2021. 12. 24.
[Leetcode] 210. Course Schedule II 문제 : https://leetcode.com/problems/course-schedule-ii/ 총 numCourses 개의 수강해야 하는 강좌가 있으며 0 ~ numCourses-1 의 레이블로 지정되어 있다. prerequisites[i] = [ai, bi] 로 이루어진 prerequisites 배열이 있다. 이는 ai 강좌를 수강하고 싶은 경우 bi 과정을 먼저 수강해야 함을 의미한다. 모든 강좌들을 마치기 위해 수강해야 하는 강좌의 순서를 구해라. 만일 모든 강좌들을 수강할 수 없다면 빈 배열을 반환해라. adj[i] = i번째 강좌를 수강해야만 들을 수 있는 강좌의 번호들 degree[i] = i번 강좌를 수강하기 위해 수강해야 하는 강좌들의 개수 prerequisites을 탐색하며 위 배열들.. 2021. 12. 23.

티스토리툴바