[알고리즘] 색 정렬
3506 단어 네덜란드 국기 문제알고리즘네덜란드 국기 문제
책 풀이
class Solution:
def sortColors(self, nums: List[int]) -> None:
mid = 1
i, j = 0, 0
k = len(nums)
while j < k:
if nums[j] < mid:
nums[i], nums[j] = nums[j], nums[i]
i += 1
j += 1
elif nums[j] > mid:
k -= 1
nums[k], nums[j] = nums[j], nums[k]
else:
j += 1
이 문제는 다익스트라가 1976년에 제안한 네덜란드 국기 문제와 동일한 문제로 퀵 정렬의 개선 아이디어와도 관련이 깊다.
i, k를 양쪽 포인터로 두고, j가 이동하면서 mid 값을 기준으로 스왑하는 형태다.
Author And Source
이 문제에 관하여([알고리즘] 색 정렬), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@injoon2019/알고리즘-색-정렬저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)