문제
52장 카드 덱이 있다. 초기 순서는 Clubs 2Ace, Diamonds 2Ace, Hearts 2Ace, Spades 2Ace 순이다.
n개의 셔플 패턴이 정의된다. 각 패턴은 52개의 정수로, i번째 위치에 적힌 숫자 j는 셔플 전 j번째 위치의 카드가 셔플 후 i번째 위치로 이동함을 의미한다.
셔플 번호가 순서대로 주어지면, 모든 셔플을 적용한 후 최종 카드 순서를 출력한다.
입력
- 첫 줄: n (셔플 패턴 수)
- 이후 n개의 패턴: 각 52개의 정수
- 이후 셔플 번호 시퀀스 (EOF까지)
출력
각 셔플 적용 후 52장의 카드를 "Value of Suit" 형식으로 출력한다. 셔플 결과 사이에 빈 줄을 넣는다.
예제
| 입력 | 출력 |
|---|---|
1 2 1 3 4 ... 52 1 | 3 of Clubs 2 of Clubs 4 of Clubs ... |
풀이
셔플 패턴을 미리 저장하고, 주어진 셔플 번호를 순서대로 적용하여 덱을 갱신한다.
- n개의 셔플 규칙
rules[i][j]를 읽는다.rules[t][i] = j는 t번 셔플에서 기존 j번 위치 카드가 i번 위치로 이동함을 의미한다. - 초기 덱
current_deck[i] = i(1~52)로 설정한다. - 셔플 번호 t를 읽을 때마다
next_deck[i] = current_deck[rules[t][i]]로 새 덱을 구성한다. - 카드 번호를 suit(0
3)과 value(012)로 변환하여 출력한다.
핵심 아이디어: 셔플은 순열 합성이다. rules[t]가 위치 매핑을 정의하고, 현재 덱에 순열을 적용하면 새 덱이 된다. 카드 번호 k에서 suit는 (k-1) / 13, value는 (k-1) % 13으로 변환한다.
코드
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int rules[101][53];
int current_deck[53], next_deck[53];
string card_suits[4] = {"Clubs", "Diamonds", "Hearts", "Spades"};
string card_values[13] = {"2", "3", "4", "5", "6", "7", "8", "9", "10", "Jack", "Queen", "King", "Ace"};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
if (!(cin >> n)) return 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= 52; j++) {
cin >> rules[i][j];
}
}
for (int i = 1; i <= 52; i++) {
current_deck[i] = i;
}
int t;
while (cin >> t) {
for (int i = 1; i <= 52; i++) {
next_deck[i] = current_deck[rules[t][i]];
}
for (int i = 1; i <= 52; i++) {
current_deck[i] = next_deck[i];
int val_idx = (current_deck[i] - 1) % 13;
int suit_idx = (current_deck[i] - 1) / 13;
cout << card_values[val_idx] << " of " << card_suits[suit_idx] << "\n";
}
cout << "\n";
}
return 0;
}복잡도
- 시간: O(n * 52 + S * 52) — 셔플 패턴 입력 O(n * 52), 각 셔플 적용 O(52), S는 셔플 횟수
- 공간: O(n * 52) — 셔플 규칙 저장 배열