BOJ: 숫자 할리갈리 게임(20923) [C++]

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

20923번: 숫자 할리갈리 게임

 

카드를 위에서 뺐다가 뒤집어서 밑에다 넣기도 하고 그러는 문제라 덱 자료구조를 사용한다.

문제에서 시키는 대로 구현하면 되긴 하는데, 처음에 카드를 둘이 같이 내는 걸로 문제를 잘못 읽어서(...) 헛짓거리를 했고... 문제에서 준 2번째 테스트케이스가 왜 수연 승인지 이해가 안 가서 좀 고생했다. '게임 진행 도중 자신의 덱에 있는 카드의 수가 0개가 되면 상대방이 승리한 것으로 본다' 라는 조건 때문이었다. 도도가 5를 내도 내는 순간 자기는 카드를 0장 가지고 있는 꼴이 되므로 패배하는 걸로 처리되는 모양이다.

그래서 자신의 카드 덱이 비어있는지 검사하는 식을 카드 내는 부분의 다음에 배치했더니 해결되었다.

 

덱 위에 쌓여 있는 것을 front로 두고 풀었다.

그라운드에 있는 카드를 가져올 때는, 뒤집어서 덱 아래(back)로 합쳐야 하므로 지금 front에 있는 것이 back으로 가야 한다. 그러니 그라운드의 back부터 pop해서 차례로 덱의 back에 넣어준다. (그라운드의 front가 덱의 back이 될 수 있도록)

 

m번의 게임을 실행하는 동안 반복문 종료조건(어느 한쪽이라도 가진 카드 수가 0이 됨)이 만족되지 않았다면, 마지막에 남아 있는 카드 수로 승패를 결정한다.

 

구현 자체는 크게 어렵지 않았으나 이런저런 케이스를 생각해보느라 시간을 많이 잡아먹었다...

 

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

string playGame(deque<int>dodo, deque<int>su, int n, int m) {
    //도도와 수연의 그라운드
    deque<int>dodo_ground;
    deque<int>su_ground;
    string answer;
    
    //1이면 도도 턴 -1이면 수연 턴
    int turn = 1;
    //도도와 수연이의 현재 패 초기화(관련없는 숫자로...)
    int do_card=100, su_card=100;

    for (int i = 0; i < m; i++) {

        //도도의 턴
        if (turn == 1) {
            //도도 패 내려놓음
            do_card = dodo.front();
            dodo.pop_front();
            dodo_ground.push_front(do_card);
        }
        
        //수연의 턴
        if (turn == -1) {
            su_card = su.front();
            su.pop_front();
            su_ground.push_front(su_card);
        }

        //다음 턴으로 넘어가면 카드 내는 사람 교체
        turn *= -1;

        //종료 조건
        if (dodo.empty() && !su.empty()) { //도도 카드가 다 떨어짐
            return "su";
        }
        else if (su.empty() && !dodo.empty()) { //수연 카드가 다 떨어짐
            return "do";
        }
        else if (dodo.empty() && su.empty()) { //둘 다 떨어짐
            return "dosu";
        }

        //수연이가 치는 조건 : 합이 5고 어느 한쪽의 그라운드도 비어있지 않을 때
        if (!dodo_ground.empty() && !su_ground.empty() && do_card + su_card == 5) { //합이 5면 수연이가 침
            //도도 그라운드에 있는 카드더미를 뒤집어 자신의 덱 아래로 합침
            //그라운드에 있는걸 뒤집어 합쳐야 하니까 pop back
            while (!dodo_ground.empty()) {
                int tmp = dodo_ground.back();
                dodo_ground.pop_back();
                su.push_back(tmp);
            }
            //자기 그라운드에 있는 카드더미도 그 아래로 합침
            while(!su_ground.empty()) {
                int tmp = su_ground.back();
                su_ground.pop_back();
                su.push_back(tmp);
            }
        }
        //도도가 치는 조건 : 현재 패에 5가 등장했을 때
        else if ( (dodo_ground.size() && do_card == 5) || (su_ground.size() && su_card == 5)) { //패에 5가 나오면 도도가 침
            //수연 그라운드의 카드더미 뒤집어 합침
            while (!su_ground.empty()) {
                int tmp = su_ground.back();
                su_ground.pop_back();
                dodo.push_back(tmp);
            }
            //자기 그라운드에 있는 카드더미도 그 아래로 합침
            while (!dodo_ground.empty()) {
                int tmp = dodo_ground.back();
                dodo_ground.pop_back();
                dodo.push_back(tmp);
            }
        }
        //아무도 종 안 치면 그대로 진행
        else {
            continue;
        }
    }

    //m번의 게임이 끝난 뒤 승리 여부 결정
    if (dodo.size() > su.size()) answer = "do";
    else if (dodo.size() < su.size()) answer = "su";
    else answer = "dosu";

    return answer;
}

int main() {
    int n, m;
    cin >> n >> m;

    //도도와 수연이의 카드 저장할 덱
    deque<int>dodo;
    deque<int>su;
    for (int i = 0; i < n; i++) {
        //카드더미의 위 = front
        int d, s;
        cin >> d >> s;
        dodo.push_front(d);
        su.push_front(s);
    }

    cout << playGame(dodo, su, n, m);
    return 0;
}