Sort Colors
빨강, 흰색, 파랑과 같은 세 가지 색을 나타내는 0, 1 또는 2 값만 들어 있는 배열 nums가 주어집니다. 배열을 재배열해 모든 0이 먼저 오고, 그다음 모든 1이 오고, 마지막으로 모든 2가 오도록 한 뒤 반환하세요. 라이브러리의 정렬 함수를 사용하지 않고 해결하세요.
함수
- numsinteger-array
- 색상은 각각 0, 1 또는 2
- 반환값integer-array
- 같은 값들을 0부터 모두 나열한 다음, 1을 모두 나열하고, 그다음 2를 모두 나열합니다
제약 조건
1 ≤ nums.length ≤ 1.5 × 104- 모든
nums[i]는0,1또는2입니다. - 색상이 없을 수도 있고, 배열에 단일 색상만 들어 있을 수도 있습니다.
예제
- 입력
- nums = [2, 1, 0, 2, 0, 1, 1]
- 출력
- [0, 0, 1, 1, 1, 2, 2]
- 설명
- 배열에는 0이 두 개, 1이 세 개, 2가 두 개 있으므로 결과도 정확히 같습니다. 0이 두 개, 그다음 1이 세 개, 그리고 2가 두 개입니다.
- 입력
- nums = [2, 0, 2]
- 출력
- [0, 2, 2]
- 설명
- 1은 전혀 없습니다. 0 하나가 맨 앞으로 이동하고 2 두 개가 그 뒤를 따릅니다.
- 입력
- nums = [1]
- 출력
- [1]
- 설명
- 단일 값은 이미 정렬되어 있으므로 배열은 변경되지 않은 채 반환됩니다.
후속 질문
배열의 길이보다 훨씬 작은 k개의 색상이 있다면 무엇을 바꾸시겠어요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
서로 다른 값은 세 개만 나타날 수 있습니다. 이를 통해 일반적인 정렬로는 할 수 없는 어떤 작업을 할 수 있나요?
0, 1, 2의 개수를 세고 배열을 다시 작성하는 작업은 두 번의 순회로 이루어집니다. 한 번의 순회에서는 세 영역이 동시에 커지는 모습을 떠올려 보세요. 앞쪽에는 0, 뒤쪽에는 2, 그 사이에는 1이 있습니다.
세 개의 인덱스
low,mid,high를 유지하세요.nums[mid]를 읽으세요. 0이면low와 교환하고, 2이면high와 교환하며, 1이면 그대로 둡니다.high와 교환한 후에는 같은 위치를 다시 읽으세요.
풀이
0, 1, 2만 나타날 수 있으므로 이를 세고 배열을 두 번에 걸쳐 다시 쓸 수 있습니다. 0이 끝나는 위치와 2가 시작되는 위치를 표시하는 세 개의 포인터를 사용하면 한 번에 처리하면서 읽는 각 값을 제자리에 놓을 수 있습니다. 이 분할 방식이 네덜란드 국기 알고리즘입니다.
손으로 버블 정렬하기
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
라이브러리 정렬을 사용하지 않는다면 기본 방식은 직접 작성하는 정렬이다. 버블 정렬은 배열을 순회하며 순서가 잘못된 이웃한 두 값을 서로 바꾼다. 각 패스는 만나는 값 중 가장 큰 값을 끝까지 옮기므로, n-1번의 패스가 끝나면 모든 위치가 확정된다.
비교 횟수는 약 n²/2회다. n = 1.5 × 10^4일 때 10^8회를 넘으며, 비교 과정 어디에서도 값이 세 개뿐이라는 사실을 활용하지 않는다.
알고리즘
- 배열을 n-1회 순회합니다.
- 각 순회에서 아직 최종 위치에 도달하지 않은 모든 이웃 쌍
nums[j]와nums[j + 1]을 비교하고, 왼쪽 값이 더 크면 서로 바꿉니다. - 0부터 세었을 때
done번째 순회가 끝나면 마지막done + 1개 위치에 최종 값이 놓이므로, 다음 순회는 그 앞에서 멈춥니다. nums를 반환합니다.
def sortColors(nums):
n = len(nums)
for done in range(n - 1):
# One pass: the largest value left so far bubbles to index n-1-done.
for j in range(n - 1 - done):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
return nums각 색상의 개수를 센 다음 다시 작성하세요
핵심 아이디어
같은 값은 서로 바꿔도 되므로 개수만 중요합니다. 첫 번째 예시에서는 0 두 개, 1 세 개, 2 두 개의 개수를 세면 무엇을 옮기기도 전에 답이 정해집니다.
배열을 한 번 훑어 각 값의 개수를 센 다음, 배열의 시작부터 덮어씁니다. count[0]개의 0, count[1]개의 1, count[2]개의 2를 씁니다. 이것이 계수 정렬입니다. 두 번의 순회와 세 개의 카운터로 O(n) 시간과 O(1) 공간을 사용합니다.
알고리즘
- 모든 값을 0으로 설정한 카운터 3개를 만드세요.
- 모든 값을 읽고 해당 카운터를 1씩 증가시키세요.
- 처음부터
count[0]개의 0을 쓴 다음,count[1]개의 1을 쓰고, 이어서count[2]개의 2를 쓰세요. nums를 반환하세요.
def sortColors(nums):
count = [0, 0, 0] # how many 0s, 1s and 2s
for x in nums:
count[x] += 1
i = 0
for color in range(3):
for _ in range(count[color]):
nums[i] = color
i += 1
return nums세 개의 포인터를 사용하는 한 번의 순회(네덜란드 국기 문제)
핵심 아이디어
읽으면서 세 구간을 확장하세요. low 앞의 모든 값은 0이고, low부터 mid 직전까지의 모든 값은 1이며, high 뒤의 모든 값은 2이고, nums[mid]부터 nums[high]까지는 아직 읽지 않은 구간입니다.
nums[mid]를 읽으세요. 1은 이미 해당 구간에 있으므로 mid를 앞으로 이동합니다. 0은 nums[low]와 서로 바꾸고 둘 다 앞으로 이동합니다. low에서 돌아온 값은 1이거나, 아직 1을 본 적이 없다면 같은 0이므로 제자리에 있게 됩니다. 2는 nums[high]와 서로 바꾸고 high를 뒤로 이동하지만, high에서 온 값은 아직 읽지 않은 값이므로 mid는 그대로 둡니다.
각 단계에서 mid는 앞으로 이동하거나 high는 뒤로 이동하므로, 루프는 n단계 후에 끝납니다. [2, 0, 2]에서는 첫 번째 2가 마지막 값과 바뀌고 high는 1로 줄어듭니다. 인덱스 0에는 여전히 2가 있으므로 0과 바뀝니다. 그러면 0은 제자리에 있게 되어 [0, 2, 2]가 됩니다.
알고리즘
low = 0,mid = 0으로 설정하고high는 마지막 인덱스로 설정합니다.mid ≤ high인 동안nums[mid]를 읽습니다.- 값이 0이면
nums[low]와 교환하고low와mid를 오른쪽으로 한 칸 이동합니다. - 값이 1이면
mid를 오른쪽으로 한 칸 이동합니다. - 값이 2이면
nums[high]와 교환하고high를 왼쪽으로 한 칸 이동합니다.mid는 그대로 둡니다. nums를 반환합니다.
def sortColors(nums):
# nums[:low] are 0s, nums[low:mid] are 1s, nums[high + 1:] are 2s.
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else:
# The value swapped in from high is unread, so mid stays.
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1
return nums
함정과 경계 사례
high와 교환한 뒤mid를 앞으로 이동하는 경우. 도착한 값은 아직 읽지 않은 값입니다.[1, 2, 0]에서는 2가 0과 교환되며, 0을 건너뛰면[1, 0, 2]가 반환됩니다.mid < high인 동안 반복하는 경우. 두 인덱스가 만나면 해당 위치의 값은 아직 읽지 않은 값입니다.[1, 0]에서는 0을 읽기 전에 반복문이 종료되어[1, 0]이 반환됩니다.- 부호 없는 인덱스에서
high가 0보다 작아지도록 두는 경우.[2]처럼 2만 있는 배열은high를 -1로 만들며, 이 값은 Rust의usize에서 언더플로를 일으킵니다. 대신high를 아직 읽지 않은 부분의 한 칸 뒤에 두세요.
자주 묻는 질문3
네덜란드 국기 문제란 무엇인가요?
Edsger Dijkstra가 제시한 문제는 빨강, 흰색, 파랑의 네덜란드 국기 색상으로 된 객체들을 한 줄로 배열하고, 교환만 사용해 한 번의 순회로 각 색상끼리 모으는 것입니다. Sort Colors는 0, 1, 2를 사용하는 같은 문제이며, 그의 해법은 세 개의 포인터를 이용한 분할입니다.
Sort Colors의 시간 및 공간 복잡도는 무엇인가요?
한 번 순회하는 해결책은 읽지 않은 부분을 매 단계마다 한 셀씩 줄이므로 O(n) 시간에 실행됩니다. 추가 공간은 O(1)을 사용합니다. 인덱스 세 개와 교환을 위한 임시 값이 필요합니다. 계수 정렬도 동일한 복잡도를 가지지만 배열을 두 번 읽습니다.
Sort Colors에 계수 정렬을 사용하는 것이 적절한 답일까요?
시간 복잡도 O(n)과 공간 복잡도 O(1)을 만족하며, 많은 면접관이 이를 첫 번째 답변으로 받아들입니다. 다음에는 한 번만 순회하는 방법을 요구받을 수 있습니다. 파티션이 세 그룹으로만 나뉘므로 색상이 많을 때는 계수하는 방법이 더 적합합니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def sortColors(nums):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자
nums = [2, 1, 0, 2, 0, 1, 1]
예상 출력
[0, 0, 1, 1, 1, 2, 2]