문제 소개
빨강(R), 초록(G), 파랑(B) 세 가지 색상으로 이루어진 리스트가 있다고 가정해 보겠습니다. 리스트 안에서 서로 다른 두 색상이 나란히 인접해 있다면, 이 두 아이템을 합쳐서 나머지 세 번째 색상의 아이템 하나로 바꿀 수 있습니다. 우리가 구해야 하는 것은 이러한 변환을 임의의 순서로 반복 수행했을 때, 마지막에 남길 수 있는 아이템의 최소 개수입니다.
예를 들어 입력이 colors = ["G", "R", "G", "B", "R"]라고 한다면, 아래 그림과 같은 과정을 거쳐 아이템 하나만 남길 수 있으므로 결과는 1이 됩니다.
문제 해결 접근 방식
이 문제는 각 색상에 특정 숫자를 대응시킨 뒤 배타적 논리합(XOR)의 성질을 이용하면 선형 시간에 해결할 수 있습니다. 알고리즘의 진행 순서는 다음과 같습니다.
- n := colors 리스트의 크기
- colors에 한 가지 색상만 존재한다면 n을 반환 (변환이 일어날 수 없음)
- n <= 1이라면 n을 반환
- x := 0 으로 초기화
- d := {"R": 1, "G": 2, "B": 3} 형태의 매핑 생성
- colors의 각 색상 c에 대해 x := x XOR d[c] 수행
- x가 0이면 2를, 그렇지 않으면 1을 반환
XOR 불변량이 작동하는 이유
비트로 표현하면 R = 1(01), G = 2(10), B = 3(11)이며, 이때 서로 다른 두 색의 XOR 값은 정확히 나머지 세 번째 색과 일치합니다. 예를 들어 01 XOR 10 = 11이므로 R과 G를 합쳐 B를 만드는 규칙과 완벽하게 대응됩니다.
따라서 인접한 두 색을 지우고 세 번째 색을 새로 넣더라도 리스트 전체의 XOR 값은 절대 변하지 않습니다. 즉, XOR 값은 이 문제의 불변량(invariant)입니다. 최종적으로 아이템이 하나만 남았다면 전체 XOR은 0이 아니어야 하고, 두 개가 남았다면 두 아이템은 같은 색이어야 하므로 전체 XOR은 0이 됩니다. 처음부터 모든 색상이 동일하다면 어떤 변환도 일어날 수 없으므로 그대로 n을 반환하면 됩니다.
파이썬 구현 예제
아래 구현 예제를 통해 더 쉽게 이해할 수 있습니다.
class Solution:
def solve(self, colors):
n = len(colors)
if len(set(colors)) == 1:
return n
if n <= 1:
return n
x = 0
d = {"R": 1, "G": 2, "B": 3}
for qux in colors:
x ^= d[qux]
return 2 if x == 0 else 1
ob = Solution()
colors = ["G", "R", "G", "B", "R"]
print(ob.solve(colors))
입력
["G", "R", "G", "B", "R"]
출력
1
복잡도 분석
리스트를 한 번만 순회하면 되므로 시간 복잡도는 O(n)이며, 상수 개의 변수만 사용하므로 공간 복잡도는 O(1)입니다.