| array - sort colors
> 문제
위와 같은 배열이 있는 경우 작은 수 부터 큰 수 순서로 정렬하여야 합니다.
> solution1_count
3개의 빈 변수를 만들어 오른쪽으로 옮겨가며 각 숫자의 갯수를 기록한 후 output으로 각각의 갯수만큼 차례대로 채운 배열을 리턴하면 됩니다.
time complexity는 O(n)가 됩니다.
> solution2_sort colors
in-place swap방식
3개의 포인터를 만들어 다음과 같은 규칙을 정해줍니다.
'A 포인터는 0을 받으면 오른 쪽으로 한 칸'
'B 포인터는 2를 받으면 왼쪽으로 한 칸'
'C 포인터는 오른쪽으로 이동하면서 0을 만나면 A포인터와 swap, 2를 만나면 B포인터와 swap합니다.'
C 포인터가 0을 만났기 때문에 A 포인터가 가리키는 숫자와 스왑을 합니다.
그리고 A 포인터와 B 포인터는 오른쪽으로 한 칸 이동합니다.
C 포인터가 B 포인터와 스왑을 한 경우 A 포인터와의 스왑과는 달리 C 포인터가 가리키는 숫자는 0, 1, 2 모두 가능하므로 스왑 후의 값을 다시 한 번 체크해줘야 함을 주의해야 합니다.
C 포인터가 1을 가리키는 경우 스왑 없이 오른쪽으로 이동합니다.
위와 같은 과정을 반복하면 왼쪽부터 0 ~ 2의 순서로 정렬되며 최종적으로 C 포인터와 B 포인터가 교차(C <= B)되면 operation이 종료 되도록 합니다.
time complexity는 O(n)이 됩니다.
Quick sort의 원리와 다를 바 없으며 partitioning에 대한 내용입니다.
▶︎ code
nums = [1, 0, 2, 2, 0, 1, 2, 1, 0]
def sort_colors(arr):
a_pointer = 0
b_pointer = len(arr) - 1
c_pointer = 0
while c_pointer <= b_pointer:
print('check loop_top:::', 'arr:', arr, '/', 'c_pointer:', c_pointer)
if arr[c_pointer] == 0:
arr[a_pointer], arr[c_pointer] = arr[c_pointer], arr[a_pointer]
a_pointer += 1
c_pointer += 1
elif arr[c_pointer] == 2:
arr[c_pointer], arr[b_pointer] = arr[b_pointer], arr[c_pointer]
b_pointer -= 1
else: # arr[c_pointer] == 1
c_pointer += 1
print('check loop_bot:::', 'arr:', arr, '/', 'c_pointer:', c_pointer)
print(sort_colors(nums))
print(f'result: {nums}')
출처: 코드없는 프로그래밍
Author And Source
이 문제에 관하여(| array - sort colors), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@max-sum/algorithm-array-sort-colors저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)