nums라는 숫자 리스트가 주어져 있고, 이 리스트는 한 노선에 있는 버스 정류장들을 나타낸다고 가정해 봅시다. 여기서 nums[i]는 버스가 i번째 정류장에 반드시 도착해야 하는 시간을 의미합니다. 버스는 뒤로 돌아갈 수 없이 앞으로만 이동할 수 있으므로, 우리는 모든 정류장을 지나가기 위해 필요한 최소 버스 대수를 구해야 합니다.
예를 들어 입력이 nums = [1, 2, 7, 9, 3, 4]라고 한다면, 출력은 2가 됩니다. 한 대의 버스가 시간순으로 [1, 2, 3, 4] 정류장을 순서대로 지나갈 수 있고, 또 다른 한 대가 [7, 9]를 담당할 수 있기 때문입니다.
문제 해결 접근 방식
이 문제는 그리디(Greedy) 방식으로 해결할 수 있습니다. 아직 처리되지 않은 정류장을 발견하면 새로운 버스를 배정하고, 그 버스가 이후에 지나갈 수 있는(도착 시간이 점점 증가하는) 정류장들을 함께 묶어 처리하는 것입니다.
구체적인 단계는 다음과 같습니다.
- ans := 0 으로 초기화합니다.
- seen := nums와 길이가 같으며 false로 채워진 리스트를 만듭니다. 각 정류장의 방문 여부를 추적합니다.
- nums의 각 인덱스 i와 값 n에 대해 반복합니다.
- 만약 seen[i]가 false라면:
- seen[i] := True 로 표시합니다.
- ans := ans + 1 (새로운 버스가 필요함)
- prev := n 으로 설정합니다.
- j를 i+1부터 nums의 끝까지 반복합니다.
- 만약 nums[j] > prev 이고 seen[j]가 false라면:
- seen[j] := True 로 표시합니다.
- prev := nums[j] 로 갱신합니다.
- 만약 nums[j] > prev 이고 seen[j]가 false라면:
- 만약 seen[i]가 false라면:
Python 구현 예제
다음 구현을 통해 더 잘 이해할 수 있습니다.
class Solution: def solve(self, nums): ans = 0 seen = [False] * len(nums) for i, n in enumerate(nums): if not seen[i]: seen[i] = True ans += 1 prev = n for j in range(i+1, len(nums)): if nums[j] > prev and not seen[j]: seen[j] = True prev = nums[j] return ans ob = Solution() nums = [1, 2, 7, 9, 3, 4] print(ob.solve(nums))
입력
[1, 2, 7, 9, 3, 4]
출력
2
동작 원리 정리
위 코드는 배열을 한 번씩 순회하면서 아직 방문하지 않은 정류장마다 새로운 버스를 배정하고, 해당 버스가 도착 시간이 증가하는 순서로 지나갈 수 있는 후속 정류장들을 함께 처리합니다. 이 과정에서 생성된 버스의 총 개수가 곧 문제의 정답이 됩니다. 시간 복잡도는 O(n²)이며, n은 정류장의 개수입니다.