[BOJ] 행운의 바퀴(2840)

[백준(BOJ)] 행운의 바퀴(2840) C++

문제 : BOJ_2840번 행운의 바퀴

문제 설명

구현

저에게는 어려운 구현 문제였습니다.

N개의 숫자가 원형으로 쓰여있는 원형 판을 항상 시계방향으로 돌립니다.

이때 돌아간 칸의 수와 가리키는 칸에 쓰여있는 알파벳 문자가 K 번 입력됩니다.

이를 바탕으로 마지막으로 가리키는 칸부터 순서대로 원형의 알파벳을 출력하는 문제입니다.

---

Solution

저는 우선 크기에 맞는 벡터 배열을 할당했습니다.

또 원형 판을 하나의 배열로 생각했고, 순회 시켰습니다.

이때 원형 판이 시계방향으로 돌아간다는 것은 배열의 입장에선 마이너스로 도는 것이기 때문에 회전한 칸 수만큼 마이너스를 하여 문자를 넣어주었습니다.

문제가 어려웠던 이유는 중복된 값을 처리하는 것이었습니다.

• 문자를 넣어줄 때, 문자를 전에 넣은 칸이 아닌데 넣을 문자와 다른 문자가 있을 때
• 문자를 모두 넣은 뒤 서로 다른 인덱스에 같은 문자가 들어가 있을 때
• 또한 회전수가 원형 판 칸의 크기를 넘길 수 있으므로 N으로 나눈 나머지로 처리해 주어야 합니다.*
  
  위 두 가지를 모두 처리해 주어야 합니다.

---

Description

• 처음 배열에 모두 문자열 '?'를 할당해 주었습니다.
• 회전수 cnt를 받은 뒤 cnt %= N;를 실행하고 처리해 주었습니다.

---

#include <iostream>
#include <vector>
using namespace std;
int main(void) {
    int N, K;
    cin >> N >> K;
    vector<char> adj(N);
    for (int i = 0; i < N; i++) adj[i] = '?';
    int now = 0;
    for (int i = 0; i < K; i++) {
        int cnt;
        char value;
        cin >> cnt >> value;
        cnt %= N;
        now -= cnt;
        if (now < 0) now += N;
        if (adj[now] != '?' && adj[now] != value) {
            cout << "!\n";
            return 0;
        }
        else adj[now] = value;
    }
    for (int i = 0; i < N-1; i++) {
        for (int j = i + 1; j < N; j++) {
            if (adj[i] != '?' && adj[i] == adj[j]) {
                cout << "!\n";
                return 0;
            }
        }
    }
    int rot = N;
    while (rot--) {
        cout << adj[now];
        now++;
        if (now == N) now = 0;
    }
    cout << '\n';
    return 0;
}