[백준] 2840번: 행운의 바퀴 - C++

문제

상덕이는 최근에 행운의 바퀴를 구매했다. 상덕이는 바퀴의 각 칸에 알파벳 대문자를 아래 그림과 같이 적었다.

바퀴에 같은 글자는 두 번 이상 등장하지 않는다. 또, 바퀴는 시계방향으로만 돌아간다. 바퀴 옆에는 화살표가 있는데, 이 화살표는 항상 한 곳을 가리키고 있으며, 돌아가는 동안 가리키는 글자는 바뀌게 된다. 위의 그림에서는 H를 가리키고 있다.

상덕이는 바퀴를 연속해서 K번 돌릴 것이다. 매번 바퀴를 돌릴 때 마다, 상덕이는 화살표가 가리키는 글자가 변하는 횟수와 어떤 글자에서 회전을 멈추었는지를 종이에 적는다.

희원이는 상덕이가 적어놓은 종이를 발견했다. 그 종이를 바탕으로 상덕이가 바퀴에 적은 알파벳을 알아내려고 한다.

상덕이가 종이에 적어놓은 내용과 바퀴의 칸의 수가 주어졌을 때, 바퀴에 적어놓은 알파벳을 알아내는 프로그램을 작성하시오.

 

입력

첫째 줄에 바퀴의 칸의 수 N과 상덕이가 바퀴를 돌리는 횟수 K가 주어진다. (2 ≤ N ≤ 25, 1 ≤ K ≤ 100)

다음 줄부터 K줄에는 바퀴를 회전시켰을 때 화살표가 가리키는 글자가 몇 번 바뀌었는지를 나타내는 S와 회전을 멈추었을 때 가리키던 글자가 주어진다. (1 ≤ S ≤ 100)

 

출력

첫째 줄에 마지막 회전에서 화살표가 가리키는 문자부터 시계방향으로 바퀴에 적어놓은 알파벳을 출력한다. 이때, 어떤 글자인지 결정하지 못하는 칸은 '?'를 출력한다. 만약, 상덕이가 적어놓은 종이에 해당하는 행운의 바퀴가 없다면 "!"를 출력한다. 

---

애를 많이 먹었던 문제...

문제 해석이 어렵기도 했고 예외처리 조건이 빡셌다.

 

나름의 논리로 풀었던 답안이 있었는데, 모든 예외처리를 해줬음에도 어떤 경우에서 걸리는지 반례를 못찾아서 결국 제출은 구글링해서 참고한 답안으로 했다.

생각해줘야 하는 경우는 다음과 같다.

 

1. 새로 들어가야 할 칸에 같은 문자 또는 ?이 아닌 다른 문자가 들어가있는 경우
2. 중복된 문자가 같은 칸이 아닌 다른 칸에 들어있는 경우

가장 마지막 문자를 기준으로 출력하는 것이기 때문에 이에만 더 유의해주면 된다.

 

#include <cstdio>
#include <cstring>
#include <vector>
#define MAX 26

using namespace std;

vector<pair<int, char> > roulette;

int main(void) {
    int N, K;
    scanf("%d %d", &N, &K);

    roulette.resize(K);
    for(int i = 0; i < K; i++) {
        scanf("%d %c", &roulette[i].first, &roulette[i].second);
    }

    char wheel[MAX];
    memset(wheel, '?', MAX);

    int alphabet[26] = { 0 }; // 중복성 체크용

    wheel[0] = roulette[K - 1].second;
    int pos = 0;
    for(int i = K - 2; i >= 0; i--) {
        int index = (pos + roulette[i + 1].first) % N;
        if(wheel[index] != roulette[i].second && wheel[index] != '?') {
            printf("!\n");
            return 0;
        }
        wheel[index] = roulette[i].second;
        pos = index;
    }

    for(int i = 0; i < N; i++) { // 같은 글자 두 번 이상 등장하는지 검사
        alphabet[wheel[i] - 'A']++;
        if(alphabet[wheel[i] - 'A'] > 1 && wheel[i] != '?') {
            printf("!\n");
            return 0;
        }
    }

    for(int i = 0; i < N; i++) {
        printf("%c", wheel[i]);
    }
    printf("\n");
    return 0;
}

 

코드

#include <cstdio>
#include <cstring>
#define MAX 25

int main(void) {
    int N, K;
    scanf("%d %d", &N, &K);

    char roulette[MAX];
    memset(roulette, '?', MAX);

    int index = 0;
    for(int i = 0; i < K; i++) {
        int pos;
        char c;
        scanf("%d %c", &pos, &c);

        pos %= N;
        if(index - pos < 0) index = index - pos + N;
        else index -= pos;

        if(roulette[index] != c && roulette[index] != '?') {
            printf("!\n");
            return 0;
        }

        roulette[index] = c;
    }

    for(int i = 0; i < N; i++) {
        for(int j = i + 1; j < N; j++) {
            if(roulette[i] != '?' && roulette[i] == roulette[j]) {
                printf("!\n");
                return 0;
            }
        }
    }

    for(int i = 0; i < N; i++) { // 마지막 index부터 시작
        printf("%c", roulette[(i + index) % N]);
    }
    printf("\n");

    return 0;
}