문제 이해하기
배열 nums가 주어졌을 때, 이를 left와 right라는 두 개의 하위 배열로 분할하려고 합니다. 단, 다음 세 가지 조건을 반드시 만족해야 합니다.
left의 모든 원소는 right의 모든 원소보다 작거나 같아야 합니다.
left와 right는 모두 비어 있으면 안 됩니다.
left의 크기는 가능한 한 가장 작아야 합니다.
이러한 조건대로 분할했을 때, left의 길이를 구하는 것이 이 문제의 핵심입니다.
예를 들어 입력이 [5, 0, 3, 8, 6]이라면 결과는 3입니다. left가 [5, 0, 3], right가 [8, 6]으로 나뉘며 세 조건을 모두 충족하기 때문입니다.
해결 접근 방법
이 문제는 배열을 한 번만 순회하는 O(n) 방식으로 해결할 수 있습니다. 핵심 아이디어는 두 개의 최댓값을 동시에 추적하는 것입니다.
mx : 현재 확정된 left 파티션의 최댓값
nmx : 지금까지 확인한 전체 원소 중 최댓값
temp : left 파티션의 마지막 인덱스
temp2 : 현재 순회 위치를 나타내는 카운터
알고리즘의 진행 과정은 다음과 같습니다.
첫 번째 원소는 반드시 left에 포함되어야 하므로, mx와 nmx를 첫 원소 값으로 초기화합니다.
현재 원소
i가 mx보다 크거나 같다면 일단 right 후보로 넘깁니다. 이때 i가 nmx보다 크면 nmx를 함께 갱신합니다.현재 원소
i가 mx보다 작다면 이 원소는 left에 속해야 합니다. 따라서 그동안 right 후보였던 원소들도 전부 left로 편입시켜야 합니다. 즉, temp를 temp2로 갱신하고 mx를 nmx 값으로 업데이트합니다.모든 원소를 확인한 후 temp + 1을 반환하면, 그것이 곧 left의 길이가 됩니다.
구현 예제
다음 파이썬 코드로 위 로직을 직관적으로 확인할 수 있습니다.
def solve(nums):
mx = None # left 파티션의 최댓값
nmx = None # 지금까지 본 전체 최댓값
temp = None # left의 마지막 인덱스
temp2 = 0 # 현재 위치 카운터
for i in nums:
if(mx == None):
mx = i
nmx = i
temp = temp2
temp2 += 1
continue
if(i >= mx):
temp2 += 1
if(i > nmx):
nmx = i
continue
else:
# i가 mx보다 작으면 right 후보들을 left로 편입
temp = temp2
temp2 += 1
mx = nmx
continue
return temp + 1
nums = [5,0,3,8,6]
print(solve(nums))
입력 및 실행 결과
[5,0,3,8,6]
실행하면 다음과 같은 결과가 출력됩니다.
3
정리
이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n), 추가 메모리 사용량은 O(1)로 매우 효율적입니다. 왼쪽 파티션의 최댓값(mx)과 전체 누적 최댓값(nmx)을 함께 관리하여, 특정 원소가 왼쪽으로 들어가야 하는 순간에 그동안의 오른쪽 후보들을 한꺼번에 흡수하는 방식으로 동작한다는 점이 핵심 포인트입니다.