문제 개요
고유한 숫자가 적힌 카드 한 벌(deck)이 있다고 가정해 봅시다. 우리는 이 카드 덱을 원하는 어떤 순서로든 배열할 수 있습니다. 처음에는 모든 카드가 앞면이 보이지 않는 상태(뒷면)로 한 벌에 담겨 있습니다. 이제 다음 과정을 모든 카드가 공개될 때까지 반복합니다.
- 덱에 카드가 남아 있다면, 맨 위의 카드를 꺼내 공개하고 제거합니다.
- 덱에 아직 카드가 남아 있다면, 그 다음 맨 위의 카드를 덱의 맨 아래로 옮깁니다.
- 아직 공개되지 않은 카드가 남아 있다면 첫 번째 단계로 돌아가고, 그렇지 않으면 과정을 종료합니다.
우리가 구해야 할 것은 이 과정을 수행했을 때 카드가 오름차순(증가하는 순서)으로 공개되도록 만드는 덱의 배치 순서입니다. 결과의 첫 번째 요소는 덱의 맨 위에 해당한다고 가정합니다.
예제 살펴보기
입력이 [17,13,11,2,3,5,7]이라면 출력은 [2,13,3,11,5,17,7]이 됩니다.
덱을 [2,13,3,11,5,17,7]로 재배열했다고 해봅시다. 맨 위의 2를 공개하면, 다음 카드인 13은 맨 뒤로 이동하여 덱은 [3,11,5,17,7,13]이 됩니다. 이어서 3을 공개하고 같은 과정을 반복하면 덱은 [5,17,7,13,11]이 되고, 5를 공개한 뒤 맨 위 카드를 뒤로 옮기면 [7,13,11,17]이 됩니다. 같은 방식으로 덱은 [11,17,13] → [13,17] → [17] 순으로 변하고, 마지막으로 17을 공개하며 모든 카드가 오름차순(2, 3, 5, 7, 11, 13, 17)으로 드러나게 됩니다.
풀이 접근 방법
이 문제는 큐(queue)를 활용하면 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 "공개될 위치"를 미리 시뮬레이션하는 것입니다.
- 먼저 덱을 오름차순으로 정렬하고, n := 덱의 크기로 설정합니다.
- 정수형 큐 q와 크기가 n인 배열 ans를 선언합니다.
- 0부터 n-1까지의 인덱스 i를 순서대로 큐 q에 삽입합니다. (각 인덱스는 카드가 공개될 위치를 의미합니다.)
- i를 0부터 n-1까지 반복합니다.
- x := 큐의 맨 앞(front) 요소를 가져온 뒤 큐에서 제거합니다.
- ans[x] := deck[i] 로 정렬된 카드를 해당 위치에 배치합니다.
- 다시 x := 큐의 맨 앞 요소를 가져와 제거한 후,
- x를 큐의 맨 뒤에 다시 삽입합니다. (실제 게임 규칙에서 '두 번째 카드를 맨 아래로' 보내는 동작을 재현)
- 배열 ans를 반환합니다.
정렬된 카드를 작은 값부터 차례대로 실제 공개 순서대로 배치함으로써, 원하는 결과 배열을 얻을 수 있습니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> deckRevealedIncreasing(vector<int>& deck) {
sort(deck.begin(), deck.end());
int n = deck.size();
queue <int> q;
vector <int> ans(n);
for(int i = 0; i < n; i++)q.push(i);
int x;
for(int i = 0; i < n; i++){
x = q.front();
q.pop();
ans[x] = deck[i];
x = q.front();
q.pop();
q.push(x);
}
return ans;
}
};
main(){
vector<int> v1 = {17,13,11,2,3,5,7};
Solution ob;
print_vector(ob.deckRevealedIncreasing(v1));
}입력
[17,13,11,2,3,5,7]
출력
[2,13,3,11,5,17,7]
마무리
이 알고리즘은 시간 복잡도 O(n log n)(정렬 포함), 공간 복잡도 O(n)으로 효율적으로 동작합니다. 큐를 사용해 카드가 공개되는 위치 패턴을 역으로 계산하는 것이 이 문제의 핵심 포인트이며, 유사한 시뮬레이션 기반 문제에도 널리 응용될 수 있는 기법입니다.