창고에 한 줄로 늘어선 바코드가 있다고 가정해 봅시다. i번째 바코드는 barcodes[i]로 표현됩니다. 우리의 목표는 이 바코드들을 재배열하여 인접한 두 바코드가 서로 같지 않도록 만드는 것입니다. 예를 들어 입력이 [1,1,1,2,2,2]라면, 출력은 [2,1,2,1,2,1]이 되어야 합니다.
이 문제를 해결하기 위해 다음과 같은 단계를 따릅니다.
문제 해결 접근 방법
- 빈 딕셔너리(map) d를 생성합니다.
- 바코드 배열에 존재하는 숫자들의 빈도수를 d에 저장합니다.
- 빈 리스트 x를 만듭니다.
- d의 모든 키-값 쌍(숫자, 빈도수)을 x에 삽입합니다.
- 인덱스 변수 i를 0으로 초기화합니다.
- 바코드 배열과 길이가 같은 결과 리스트 res를 생성하고 0으로 채웁니다.
- x를 빈도수 기준으로 정렬합니다.
그다음 두 단계의 while 루프를 사용하여 결과를 채워 나갑니다.
- 첫 번째 루프 (짝수 인덱스): i가 0부터 시작하여 2씩 증가하면서, x의 마지막 항목(가장 빈도가 높은 숫자)을 result[i]에 배치합니다. 해당 항목의 빈도수를 1 감소시키고, 빈도수가 0이 되면 x에서 제거합니다.
- 두 번째 루프 (홀수 인덱스): i가 1부터 시작하여 2씩 증가하면서 동일한 과정을 반복합니다.
이렇게 하면 가장 빈도가 높은 숫자들이 먼저 짝수 위치(0, 2, 4...)에 배치되고, 그다음 홀수 위치(1, 3, 5...)에 배치되어 인접한 요소가 절대 같아지지 않게 됩니다. 마지막으로 완성된 result를 반환합니다.
구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
class Solution(object):
def rearrangeBarcodes(self, barcodes):
d = {}
for i in barcodes:
if i not in d:
d[i] = 1
else:
d[i] += 1
x = []
for a, b in d.items():
x.append([a, b])
i = 0
result = [0] * len(barcodes)
x = sorted(x, key=lambda v: v[1])
while i < len(result):
result[i] = x[-1][0]
x[-1][1] -= 1
if x[-1][1] == 0:
x.pop()
i += 2
i = 1
while i < len(result):
result[i] = x[-1][0]
x[-1][1] -= 1
if x[-1][1] == 0:
x.pop()
i += 2
return result
ob = Solution()
print(ob.rearrangeBarcodes([1,1,1,2,2,2]))입력
[1,1,1,2,2,2]
출력
[2, 1, 2, 1, 2, 1]
동작 원리 정리
이 알고리즘의 핵심은 빈도수 기반 그리디(greedy) 전략입니다. 가장 많이 등장한 숫자를 먼저 간격을 두고 배치함으로써, 남은 숫자들을 나머지 위치에 자연스럽게 채워 넣을 수 있습니다. 시간 복잡도는 정렬에 O(n log n), 공간 복잡도는 O(n)입니다. 이 방식은 어떤 입력에서도 인접한 두 바코드가 같아지는 경우를 방지할 수 있으며, 특정 숫자의 빈도가 전체 길이의 절반을 초과하지 않는 한 항상 유효한 해를 보장합니다.