배열 nums가 주어졌을 때, 이 배열을 여러 개의 구간(파티션)으로 나누고 각 구간을 개별적으로 정렬한 뒤 다시 이어 붙였을 때 전체가 오름차순으로 정렬된 배열이 되도록 해야 합니다. 우리가 구해야 할 것은 바로 만들 수 있는 파티션의 최대 개수입니다.
예를 들어 입력이 [3,2,4,5,5]라면 결과는 4가 됩니다. [3,2], [4], [5], [5]처럼 네 개의 구간으로 나누면, 각 구간을 정렬해 이어 붙였을 때 [2,3,4,5,5]라는 완전히 정렬된 배열을 얻을 수 있기 때문입니다.
문제 풀이 접근 방법
핵심 아이디어는 "현재 잘라낸 구간을 정렬한 결과가, 전체 배열을 정렬했을 때 해당 위치의 값들과 정확히 일치하는가?"를 확인하는 것입니다. 일치한다면 그 구간은 독립적인 파티션으로 확정할 수 있고, 일치하지 않는다면 다음 요소까지 포함하도록 구간을 넓혀야 합니다.
단계별 알고리즘
- 원본 배열을 정렬한 기준 배열 real을 만듭니다.
- 포인터 p1(구간 시작), p2(구간 끝 + 1)와 파티션 개수 c를 각각 0, 1, 0으로 초기화합니다.
- nums[p1:p2] 구간을 정렬한 임시 리스트 tmp를 만듭니다.
- tmp의 각 요소가 real의 같은 위치 값과 일치하는지 하나씩 확인합니다.
- 일치하지 않으면 flag를 False로 설정하고 p2를 1 증가시켜 구간을 확장한 뒤 내부 반복을 빠져나옵니다.
- 모두 일치하면(flag가 True이면) 하나의 파티션이 확정된 것이므로 p1을 p2로 옮기고, p2를 1 증가시키며, c를 1 증가시킵니다.
- p1이 배열 길이와 같아지거나 p2가 배열 길이를 초과하면 c를 반환합니다.
Python 구현 예제
아래 예제를 통해 실제 동작을 더 잘 이해할 수 있습니다.
def solve(nums):
real = sorted(nums)
p1, p2, c = 0, 1, 0
while True:
flag = True
tmp = sorted(nums[p1:p2])
for j in range(len(tmp)):
if tmp[j] != real[p1+j]:
flag = False
p2 += 1
break
if flag:
p1, p2 = p2, p2 + 1
c += 1
if p1 == len(nums) or p2 > len(nums):
return c
nums = [3,2,4,5,5]
print(solve(nums))
입력
{3,2,4,5,5}출력
4
동작 과정 살펴보기
[3,2,4,5,5] 예제에서 알고리즘은 다음과 같이 진행됩니다.
- 구간 [3] → 정렬 결과 [3], 기준 배열의 첫 값은 2이므로 불일치 → 구간 확장
- 구간 [3,2] → 정렬 결과 [2,3], 기준 배열의 앞 두 값 [2,3]과 일치 → 첫 번째 파티션 확정
- 구간 [4] → 기준 배열의 세 번째 값 4와 일치 → 두 번째 파티션 확정
- 구간 [5] → 네 번째 값 5와 일치 → 세 번째 파티션 확정
- 구간 [5] → 다섯 번째 값 5와 일치 → 네 번째 파티션 확정
최종적으로 4개의 파티션이 만들어지며, 함수는 4를 반환합니다.
시간 복잡도
이 방법은 구간을 확장할 때마다 부분 배열을 다시 정렬해야 하므로, 최악의 경우 O(n² log n)의 시간 복잡도를 가집니다. 배열의 크기가 매우 큰 경우에는 각 위치에서 '지금까지의 최댓값(prefix max)'과 '이후 구간의 최솟값(suffix min)'을 비교하는 방식으로 O(n) 시간에 해결할 수 있는 최적화된 알고리즘도 존재합니다.