문제 개요
카드 리스트가 주어졌을 때, 카드가 오름차순으로 공개되도록 초기 배치를 만들어야 한다고 가정해 보겠습니다. 카드는 다음과 같은 규칙에 따라 공개됩니다.
- 맨 위의 카드를 제거하여 공개한 뒤, 그다음 카드를 맨 뒤로 보냅니다.
- 카드가 모두 없어질 때까지 1번 과정을 반복합니다.
즉, 우리는 카드가 오름차순으로 공개되도록 만드는 올바른 배치 순서를 찾아야 합니다.
예시로 이해하기
예를 들어 입력이 cards = [1, 2, 3, 4, 5, 6, 7, 8]이라면, 출력은 [1, 5, 2, 7, 3, 6, 4, 8]이 됩니다. 과정을 단계별로 살펴보면 다음과 같습니다.
- 1이 공개되고, 5가 맨 뒤로 이동 → 현재 상태: [2, 7, 3, 6, 4, 8, 5]
- 2가 공개되고, 7이 맨 뒤로 이동 → 현재 상태: [3, 6, 4, 8, 5, 7]
- 3이 공개되고, 6이 맨 뒤로 이동 → 현재 상태: [4, 8, 5, 7, 6]
- 4가 공개되고, 8이 맨 뒤로 이동 → 현재 상태: [5, 7, 6, 8]
- 5가 공개되고, 7이 맨 뒤로 이동 → 현재 상태: [6, 8, 7]
- 6이 공개되고, 8이 맨 뒤로 이동 → 현재 상태: [7, 8]
- 7이 공개되고, 남은 카드는 [8] 하나뿐
- 마지막으로 8을 공개하면 종료
결과적으로 카드는 1, 2, 3, 4, 5, 6, 7, 8 순서대로 공개됩니다.
해결 접근 방법
이 문제는 시뮬레이션을 역으로 생각하면 쉽게 풀 수 있습니다. 정렬된 카드를 큐(queue)를 이용해 각자 놓여야 할 위치에 배치하는 방식입니다. 단계는 다음과 같습니다.
- 카드 리스트를 오름차순으로 정렬합니다.
- 0부터 카드 개수 - 1까지의 값을 가진 인덱스 리스트 idx를 만듭니다.
- 공개 순서를 저장할 order 리스트를 생성합니다.
- idx의 요소들을 담은 큐 q를 만듭니다.
- q가 빌 때까지 다음을 반복합니다.
- q의 앞(front) 요소를 꺼내 order에 추가합니다.
- q가 비어 있지 않다면, 앞 요소를 꺼내 다시 뒤에 추가합니다.
- 카드 개수만큼 0으로 채워진 ans 리스트를 만듭니다.
- order의 인덱스 i와 정렬된 카드를 차례대로 짝지어 ans[i]에 카드 값을 넣습니다.
- ans를 반환합니다.
Python 구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
from collections import deque class Solution: def solve(self, cards): cards.sort() idx=[i for i in range(len(cards))] order=[] q=deque(idx) while q: order.append(q.popleft()) if q: q.append(q.popleft()) ans=[0 for _ in cards] for i,card in zip(order,cards): ans[i]=card return ans ob = Solution() print(ob.solve([1, 2, 3, 4, 5, 6, 7, 8]))
입력
[1, 2, 3, 4, 5, 6, 7, 8]
출력
[1, 5, 2, 7, 3, 6, 4, 8]
복잡도 분석 및 마무리
이 알고리즘은 카드를 먼저 정렬한 뒤, 큐를 활용해 각 카드가 놓일 위치를 시뮬레이션하는 방식입니다. 시간 복잡도는 정렬 비용이 지배적인 O(n log n)이며, 공간 복잡도는 O(n)입니다. 파이썬의 collections.deque를 사용하면 앞뒤 삽입·삭제가 O(1)로 처리되므로 매우 효율적입니다. 이처럼 큐 기반 시뮬레이션은 카드 재배열 문제뿐 아니라 다양한 순서 시뮬레이션 문제에 응용할 수 있는 유용한 패턴입니다.