문제 개요
숫자로 이루어진 리스트 nums가 주어졌다고 가정해 보겠습니다. 이 리스트를 part1과 part2라는 두 부분으로 나누되, part1의 모든 요소가 part2의 모든 요소보다 작거나 같아야 한다는 조건이 있습니다. 이때 만들 수 있는 part1의 최소 길이(단, 길이가 0이 되어서는 안 됨)를 구하는 것이 목표입니다.
예를 들어 입력이 nums = [3, 1, 2, 5, 4]라면 결과는 3이 됩니다. 리스트를 part1 = [3, 1, 2]와 part2 = [5, 4]로 나누면 part1의 모든 요소가 part2의 모든 요소보다 작거나 같은 조건을 만족하기 때문입니다.
해결 절차
이 문제는 다음과 같은 단계를 거쳐 풀 수 있습니다.
- p := nums의 최솟값
- s := 0
- i를 0부터 len(nums) - 1까지 반복하며, nums[i]가 p와 같으면 s := i로 설정하고 반복을 종료합니다. 즉, 최솟값이 처음 나타나는 인덱스를 찾는 과정입니다.
- p := nums[0]부터 nums[s]까지 구간의 최댓값으로 갱신
- ans := s
- i를 s + 1부터 len(nums) - 1까지 반복하며, nums[i]가 p보다 작으면 ans := i로 갱신합니다.
- 최종적으로 ans + 1을 반환합니다.
동작 원리
이 풀이의 핵심 아이디어는 다음과 같습니다. 먼저 전체 리스트에서 최솟값이 처음 등장하는 위치 s를 찾습니다. 그 앞에는 최솟값보다 큰 요소들이 존재하므로, 유효한 분할을 위해서는 최소한 인덱스 s까지는 part1에 포함되어야 합니다. 이후 part1 후보 구간의 최댓값인 p보다 작은 요소가 뒤쪽에 나타나면, 그 요소 역시 part1에 포함되어야 하므로 분할 경계 ans를 뒤로 밀어냅니다. 마지막으로 ans + 1이 곧 part1의 최소 길이가 되며, 리스트를 앞에서부터 한 번씩 훑는 방식이라 시간 복잡도는 O(n)입니다.
구현 예제
아래 예제 코드를 통해 더 자세히 이해해 보겠습니다.
def solve(nums): p = min(nums) s = 0 for i in range(len(nums)): if nums[i] == p: s = i break p = max(nums[: s + 1]) ans = s for i in range(s + 1, len(nums)): if nums[i] < p: ans = i return ans + 1 nums = [3, 1, 2, 5, 4] print(solve(nums))
입력
[3, 1, 2, 5, 4]
출력
3