[ C++/cpp ] 백준 (2840 행운의 바퀴) ⭐구현, 시뮬레이션 💥💦

 

백준 2840번 행운의 바퀴

(실버 4)
 
https://www.acmicpc.net/problem/2840

2840번: 행운의 바퀴

 
 
(정답 코드)

#include <iostream>
#include <vector>

using namespace std;

// 시계 방향으로 바퀴가 돌면, 바퀴를 고정된 배열로 뒀을 때, 화살표는 반시계로 도는 것이다.
// 양의 방향을 반시계방향이라 가정하고, 모듈러 연산을 통해 바퀴를 채워나갈 것이다.
    
// 바퀴에 같은 글자는 두 번 이상 등장하지 않는다 !!!!!!!!

int setWheel(int n, vector<char> &wheel, const vector<pair<int, char>> &info) {
    
    wheel[0] = info[0].second; // 첫 알파벳 배열에 고정 ! 얘 기준으로 이제 돌기.알
    int arrow = 0;
    
    vector<int> use_alphabet (26, -1); // 이미 쓰인 알파벳의 인덱스 표기 !
    
    // 0번은 이미 위에서 처리함. 1번 정보부터 확인하며 배열 채우기
    for(int i=1; i<info.size(); i++) {
        
        arrow = (arrow + info[i].first) % n ; // 모듈러 연산
        
        //이미 다른값이 채워져있다면,
        if(wheel[arrow]!='?' && wheel[arrow]!=info[i].second ) { 
            return -1;    
        }
        
        // 같은 알파벳이 중복되어 또 사용된다면,
        if( use_alphabet[info[i].second-'A'] != -1 && use_alphabet[info[i].second-'A'] != arrow) {
            return -1;
        }
        
        wheel[arrow] = info[i].second;
        
        // 현재 화살표가 가리키는 인덱스. 즉 알파벳이 적힌 위치를 저장해줌 !
        use_alphabet[info[i].second-'A']=arrow; 
         
    }
    
    return arrow; // 화살표 인덱스 리턴
    
    
}

int main()
{
    
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    //입력
    int n, k, s;
    char c;
    
    cin >> n >> k ;
    vector<char> wheel (n, '?'); // 바퀴 벡터
    vector<pair<int, char>> info; // 입력 정보 저장할 pair 벡터
    
    while(k--) {
        cin >> s >> c ;
        info.push_back(make_pair(s,c));
    }
    
    
    // 연산
    char ans = setWheel (n, wheel, info);
    
    
    // 출력
    if( ans == -1 ) {
        cout << "!";
    } else {
        
        // 화살표가 가리키는 곳부터 시계방향(음의 방향) 출력
        for(int i=0; i<wheel.size(); i++) {
            
            cout << wheel[ans%n];
            
            if((--ans)<0) {
                ans += n; // 음의 방향으로 인덱스 이동하다가, 음수가 되면, 바퀴 칸 수만큼 더하기 !
            }
        }
    }

    return 0;
}

 
 
 
바퀴에 중복 글자 못 쓰이는데.. 바부같이 그걸 체크 안해서 틀렸으 ~ 
문제를 잘 읽자 !
 

---

 

📖 풀이 요약

어렵진 않은 구현 문제이다. 바퀴가 돈다니 어려워보이고 당황스럽겠지만..
배열로 구현하는 원형 큐를 떠올리면 90% 해결이다.

원형 큐를 배열로 구현하는 법

 
 
 
 
바퀴가 시계방향으로 도니까, 바퀴를 고정된 배열로 뒀을 때, 화살표는 반시계로 도는 것이다.
연산하기 편하도록 배열의 양의 방향을 반시계 방향이라 가정하고, 모듈러 연산을 통해 바퀴를 채워나갔다.

 
다만, 여기서 체크해야할 것들이 몇 개 있다.
 

1. 이미 다른 알파벳이 채워진 칸인지

처음에 다 ?로 바퀴 벡터를 초기화해뒀다. 그래서
1 ) 해당 칸의 값이 ?는 아닌데(=이미 뭐가 채워짐)
2 ) 추가할 값과 다른 값이 들어있는 지를 확인했다.
 

+) 나의 작은 실수
여기서, 처음에 한 실수가 2)를 빼먹고, 단순히 ?가 아닌지만 보고 리턴했다.
이미 뭔가 채워져있다면 리턴을 해야지 싶었는데, 예제를 보고 깨달았다. 이미 같은 값이 채워져있다면, 리턴 안해도 된다 !
 
예를 들어 3칸 짜리 바퀴인데, A가 한 칸에 채워져있다.
그런데 여기서 3칸을 돌아서 다시 A가 위치한 그 칸으로 갈 수도 있지않은가? 그래서 2)를 추가해서 맞췄다.

 
 
 

2. 한 알파벳이 다른 위치에도 중복되어 또 쓰이는지

이미 사용된 알파벳을 확인하기 위해 int 벡터를 사용하여 중복된 알파벳이 사용되는지 확인했다.
26칸짜리 int 벡터에, 해당 알파벳이 쓰인 위치를 기록해두었다.
이미 어딘가에 쓰였는데, 그게 현재 화살표가 가리키는 칸이 아니라면 리턴을 해주었다.
 
 
마지막 출력도 시계 방향이므로, 현재 가리키던 부분부터 음의 방향으로 출력을 해주어야한다 !
 
 

---

 
 
실버 4라서 구현이 어렵진 않은데 진짜.. 은근 조건이 많아서.. 꼼꼼히 봐야하는 문제이다.
체크할 것들이 은근 많아서 ..ㅇㅇ
암튼 재밌는 구현 문제였다 ㅎㅎ
 

문제 푼 흔적..ㅋㅋ

 
이제 실버 구현은 나름 빨리 풀어내는 나..
코린이에서 코등학생으로 성장한 듯. 이러다 곧 중학교 가겄다 ㅎㅎ ^^
알튜비튜 덕인 것 같다. 함수화해서 코드 쓰는 법이 많이 늘었다 헤헤... 튜터님들 쵝오 사랑해요 😍