색상 문자열로 이루어진 목록이 있다고 가정해 보겠습니다. 이 목록에는 "red", "green", "blue" 세 가지 값만 포함되어 있으며, 우리는 이 목록을 빨강(red) → 초록(green) → 파랑(blue) 순서가 되도록 재배치해야 합니다.
예를 들어 입력이 다음과 같다면,
colors = ["blue", "green", "blue", "red", "red"]
출력은 아래와 같아야 합니다.
['red', 'red', 'green', 'blue', 'blue']
해결 접근 방식
이 문제는 널리 알려진 네덜란드 국기 문제(Dutch National Flag Problem)와 유사하며, 세 개의 포인터를 활용해 한 번의 순회로 해결할 수 있습니다. 각 색상별 경계 위치를 나타내는 변수 red, green, blue를 0으로 초기화한 뒤, 목록의 문자열을 하나씩 확인하며 다음 규칙에 따라 처리합니다.
- red, green, blue 변수를 모두 0으로 초기화합니다.
- 목록의 각 문자열을 순회하며 다음을 수행합니다.
- 문자열이 "red"라면: blue, green, red 위치에 차례대로 값을 덮어쓰고 각 인덱스를 1씩 증가시킵니다.
- 문자열이 "green"이라면: blue와 green 위치에 값을 덮어쓰고 해당 인덱스를 1씩 증가시킵니다.
- 문자열이 "blue"라면: blue 위치에 값을 덮어쓰고 인덱스를 1 증가시킵니다.
- 순회가 끝나면 재배치된 목록을 반환합니다.
이 방식의 핵심은 새 문자열을 읽을 때마다 그보다 우선순위가 높은 색상들의 경계 인덱스를 함께 밀어주는 것입니다. 예를 들어 "red"를 만나면 기존에 채워져 있던 초록과 파랑 영역도 한 칸씩 뒤로 이동시켜야 하기 때문입니다. 이렇게 하면 추가 메모리 없이 제자리(in-place)에서 정렬이 완료되며, 시간 복잡도는 O(n)입니다.
구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
class Solution:
def solve(self, strs):
green = 0
blue = 0
red = 0
for string in strs:
if string == "red":
strs[blue] = "blue"
blue += 1
strs[green] = "green"
green += 1
strs[red] = "red"
red += 1
elif string == "green":
strs[blue] = "blue"
blue += 1
strs[green] = "green"
green += 1
elif string == "blue":
strs[blue] = "blue"
blue += 1
return strs
ob = Solution()
colors = ["blue", "green", "blue", "red", "red"]
print(ob.solve(colors))입력
["blue", "green", "blue", "red", "red"]
출력
['red', 'red', 'green', 'blue', 'blue']
마무리
이 알고리즘은 단 한 번의 순회(O(n))로 목록 전체를 원하는 순서로 재배치할 수 있으며, 별도의 임시 리스트를 사용하지 않기 때문에 공간 복잡도도 O(1)입니다. 세 개의 포인터를 활용한 이 패턴은 세 가지 값으로 구성된 데이터를 분류하는 다양한 문제(예: 0, 1, 2로 이루어진 배열 정렬)에도 그대로 응용할 수 있으니 꼭 기억해 두시기 바랍니다.