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

2840번: 행운의 바퀴 (acmicpc.net)

2840번: 행운의 바퀴

구현, 시뮬레이션으로 분류된 문제다.

시뮬레이션 알고리즘은

일련의 명령에 따라서 개체를 차례대로 이동시키는 것

이다. 그냥 구현이 좀 까다로운 카테고리같다.

 

반례 중

4 4
1 A
1 A
1 A
1 A

 

이걸 놓쳐서 고민을 좀 했다.

문제 조건 중 중복되는 문자가 바퀴에 있으면 안된다는 것을 확인하고 코드에 추가하니까 됐다.

 

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, k;
    cin >> n >> k;
    bool flag = true;
    vector<bool> check(26, false); // 알파벳 중복 체크
    vector<char> t(n, '?');        // 모두 ?로 초기화 함

    int p = 0; // 현재의 위치를 가르키는 포인터 역할
    while (k--)
    {
        int s;
        char c;
        cin >> s >> c;
        p += s;

        // 범위 조정
        if (p >= n)
            p %= n;

        // 빈자리가 아니고, 현재 들어온 문자와 같다면
        if (t[p] != '?' && t[p] == c)
        {
            continue;
        }
        // 빈자리가 아니고, 현재 들어온 문자와 다르거나 이전에 체크한 전적이 있다면
        else if ((t[p] != '?' && t[p] != c) || check[c - 'A'])

        {
            cout << '!';
            flag = false;
            break;
        }
        else if (t[p] == '?' && !check[c - 'A'])
        { // 빈자리라면 새롭게 할당
            t[p] = c;
            check[c - 'A'] = true;
        }
    }

    if (flag)
    {
        // cout << t[p];
        int i = p;
        do
        {
            /* code */
            cout << t[i];
            if (i == 0)
                i = n;
            i--;
        } while (i != p);
    }
    // for (auto e : t)
    // {
    //     cout << e;
    // }
}

 

이렇게 풀었고,, 학교에서 알려준 방식은 아래와 같다.

 

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

typedef pair<int, char> pic;

string arrowStartWheel(int arrow_point, int n, vector<char> &wheel)
{
    string ans = "";
    int start = arrow_point;

    do
    {
        ans += wheel[arrow_point];
        arrow_point = (arrow_point + 1) % n;
    } while (arrow_point != start);
    return ans;
}

string solution(int n, vector<pic> &record)
{
    vector<char> wheel(n, '?');    // 바퀴의 상태
    vector<bool> check(26, false); // 알파벳 중복 체크

    int idx = 0; // 포인터 역할을 하는 인덱스
    for (int i = 0; i < record.size(); i++)
    {
        int rot = record[i].X;
        int alpha = record[i].Y;
        idx = (idx - rot % n + n) % n;

        // 만약 현재 입력 문자가 이미 기입된 바퀴의 상태와 일치하면 패스
        if (wheel[idx] == alpha)
        {
            continue;
        }

        // 만약 바퀴에 문자가 정의되어있고 중복된 적이 있다면 리턴
        if (wheel[idx] != '?' || check[alpha - 'A'])
        {
            return "!";
        }
        wheel[idx] = alpha;        // 위의 조건에 걸리지 않았다면 바퀴에 새롭게 문자기입
        check[alpha - 'A'] = true; // 중복 방지 처리
    }
    return arrowStartWheel(idx, n, wheel);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, k;

    // input
    cin >> n >> k;
    vector<pic> record(k, {0, 0}); // 바퀴 회전을 기록하는 벡터
    for (int i = 0; i < k; i++)
    {
        cin >> record[i].X >> record[i].Y;
    }

    // calc & output
    cout << solution(n, record);
}

 

엉 논리는 같다.