•
문제 링크 : 
LeetCodeSort Colors - LeetCode
•
문제 설명 : 0, 1, 2로 구성된 배열을 in-place로 정렬하여 반환
•
풀이 방법
◦
2를 맨뒤로 보낸 후, 0과 1을 정렬하는 방법을 사용하였다.
•
시간복잡도 :
•
성공 코드
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
left, right = 0, len(nums) - 1
# 2를 맨 뒤로 보내는 과정
while left < right:
# 우측 포인터가 2일 경우
if nums[right] == 2:
right -= 1
# 좌측 포인터가 2, 우측 포인터가 2가 아닌(0 or 1)경우
# swap
elif nums[left] == 2 and nums[right] != 2:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
# 그 외
else:
left += 1
# 0과 1을 swap하여 정렬하는 과정
left = 0
right = right - 1 if nums[right] == 2 else right
while left < right:
# 좌측이 1, 우측이 0일 경우
# 2가 swap 되지 않도록, 0과 1만 처리하도록 명시
if nums[left] == 1 and nums[right] == 0:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
# 우측이 1일 경우, 커서 변경
if nums[right] == 1:
right -= 1
# 좌측이 0일 경우, 커서 변경
if nums[left] == 0:
left += 1
Python
복사
•
성공 코드(Solution)
0, 1의 갯수만 구한 후 순서대로 채워넣는다.
이후 나머지 공간을 전부 2로 채워놓는다.
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
zeros, ones, n = 0, 0, len(nums)
for num in nums:
if num == 0:
zeros += 1
elif num == 1:
ones += 1
for i in range(0, zeros):
nums[i] = 0
for i in range(zeros, zeros + ones):
nums[i] = 1
for i in range(zeros + ones, n):
nums[i] = 2
Python
복사