[BOJ][C++] 백준 2849번: 행운의 바퀴

https://www.acmicpc.net/problem/2840

2840번: 행운의 바퀴

 

 

문제

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

 

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

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

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

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

 

풀이

11%에서 틀렸습니다 가 뜬다면

바퀴에 같은 글자는 두 번 이상 등장하지 않는다.

ㄴ 요 조건을 잡아냈는지 생각하자

 

반례

4 4
1 A
1 B
1 C
1 A

 

 

코드

#include <iostream>
#include <vector>

using namespace std;

string solution(int n, int k) {
    vector<bool> alphabetUsed(26, false); // 사용된 알파벳 표시
    vector<char> wheel(n,'?'); // 바퀴 배열 기본값은 물음표
    
    int roll, cur=0; char c;
    for(int i=0; i<k; i++) { // 돌려돌려 돌림판
        cin >> roll >> c;
        
        cur += roll;
        cur %= n;
        
        // 같은 칸도 아닌데 이미 쓴 알파벳인 경우
        if(wheel[cur]!=c && alphabetUsed[c-'A']) {
            return "!";
        }
        
        // 같은 칸도 아닌데 이미 무언가 써있을 경우
        if(wheel[cur]!=c && wheel[cur]!='?')  {
            return "!";
        }
        
        wheel[cur] = c;
        alphabetUsed[c-'A'] = true;
    }
    
    string ans = "";
    for(int i=0; i<n; i++) {
        ans += wheel[((cur-i)+n)%n];
    }
    
    return ans;
}

int main() {
    int n,k;
    cin >> n >> k;
    
    cout << solution(n,k);
    
    return 0;
}