[백준] 20923 - 숫자 할리 갈리 게임 JAVA

자료구조 및 알고리즘 스터디 문제

 

Day2 - Non-Linear Data Structure

 

자세한 내용은 스터디 내용을 참조해주십시오.

 

---

링크

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

20923번: 숫자 할리갈리 게임

문제

인간이 가장 심심함을 느낀다는 오후 1시 22분, 도도와 수연이는 숫자 할리 갈리 게임을 하려 한다. 숫자 할리 갈리 게임의 규칙은 다음과 같다.

[숫자 할리 갈리 게임의 규칙]

1. 초기에 도도와 수연이는 각각 N장의 카드로 이루어진 덱을 배분받는다. 게임 시작 시 그라운드는 비어있는 상태이다.
덱은 숫자가 보이지 않게 카드를 뒤집어 쌓아 놓은 카드 더미를 의미한다. 도도와 수연이는 자신의 덱을 가지고 게임을 진행하게 된다.
그라운드는 도도와 수연이가 게임을 진행하며 자신이 가진 덱에서 가장 위에 있는 카드를 내려놓게 되는 땅을 의미한다. 그라운드에 카드를 내려놓을 때는 자신의 그라운드에 카드를 내려놓으며, 그라운드에 카드 더미가 존재할 경우 기존에 만들어진 카드 더미 위로 카드를 내려놓는 방식으로 진행한다.
2. 도도를 시작으로 도도와 수연이가 차례대로 그라운드에 자신이 가진 덱에서 가장 위에 위치한 카드를 그라운드에 숫자가 보이도록 내려놓는다.

 

3. 종을 먼저 치는 사람이 그라운드에 나와 있는 카드 더미를 모두 가져갈 수 있다. 종을 칠 수 있는 조건은 다음과 같다.

 

• 그라운드에 나와 있는 각각의 카드 더미에서 가장 위에 위치한 카드의 숫자 합이 5가 되는 순간 수연이가 종을 친다. 단, 어느 쪽의 그라운드도 비어있으면 안 된다.
• 그라운드에 나와 있는 각각의 카드 더미에서 가장 위에 위치한 카드의 숫자가 5가 나오는 순간 도도가 종을 친다.

 

4. 종을 쳤다면, 상대방의 그라운드에 있는 카드 더미를 뒤집어 자신의 덱 아래로 그대로 합친 후 자신의 그라운드에 있는 카드 더미 역시 뒤집어 자신의 덱 아래로 그대로 가져와 합친다.

종을 쳐서 그라운드에 있는 카드 더미를 가져가는 행위는 게임의 진행 순서에 영향을 미치지 않는다.

 5. M번 진행한 후 자신의 덱에 더 많은 카드를 지닌 사람이 승리하고 M번 진행 후 각자의 덱에 있는 카드의 개수가 같다면 비긴 것으로 본다. 게임 진행 도중 자신의 덱에 있는 카드의 수가 0개가 되는 즉시 상대방이 승리한 것으로 본다. (둘 중 한 명이 2~4번까지의 과정을 진행하는 것을 1번 진행한 것으로 본다.)

게임을 M번 진행한 후 승리한 사람은 누구일까?

입력
첫째 줄에는 도도와 수연이가 가지는 카드의 개수 N(1 <N <30,000)과 게임 진행 횟수 M(1 <M < 2,500,000)이 주어진다.

둘째 줄부터 N개의 줄에는 띄어쓰기로 구분하여 도도와 수연이가 가진 덱의 맨 아래에 위치한 카드에 적혀 있는 수부터 맨 위에 위치한 카드에 적힌 수까지 차례대로 주어진다. (각각의 카드는 1 이상 55 이하의 자연수가 적혀있다.)

출력
게임을 이긴 사람이 도도라면 do를 출력하고 게임을 이긴 사람이 수연이라면 su를 출력한다. 비겼을 경우, dosu를 출력한다.

접근방법

 받은 카드를 역순으로 한 장씩 꺼내 두고, 조건에 따라 do와 su가 가져가도록 한다. 한쪽의 카드 수가 0이 되거나, M번 게임 후, 카드가 많은 쪽이 승리한다. 단, M번 게임 후 카드의 개수가 적을 경우 비긴 경우로 dosu를 반환하는 문제이다. 해당 문제에서는 카드를 받고 꺼내는 순서와 내려놓고 가져가는 순서가 섞인다. 큐 구조로 쌓다가, 스택 구조로 빼기도하고, 스택구조로 쌓다가 큐처럼 아래쪽에서 빼기도 한다. 해당 상황을 해결하기 위해서는 두 개의 성질을 가진 덱(Deq)을 이용해야 한다. 이를 인지하고 풀이로 들어가자. 

풀이

 해당 문제에서는 카드를 이동할 때, 모두 덱 구조를 필요로 한다. 필요한 상황을 정리해보면 다음과 같다.

 

1. 카드를 분배받되, 마지막 카드부터 써야 한다. ( 본인 카드 - 스택 구조)
2. 카드를 그라운드에 내려놓을 때, 본인 그라운드 위로 쌓는다. (본인 그라운드 - 스택 구조)
3. 승리 조건에 따라 승리하였다면, 진쪽의 그라운드 카드를 뒤집어 자기 카드 밑으로 추가한다. 그 후 자신의 그라운드 카드를 뒤집은 뒤, 자기 카드 밑으로 추가한다.(본인 카드 - 큐 구조) 
4.  둘 다 승리조건에 부합하지 않는다면, 다음 게임을 진행한다.

본인 카드나 그라운드 모두 양쪽을 사용하므로, 둘다 덱 구조로 구현해야 한다.

 

아래의 그림은 Do가 승리시, 카드를 가져가는 절차를 도식화한 것이다.

Do' win procedure

 

 덱을 사용할 때에는 자신이 사용하는 방향에 대해 정의하는 것이 중요하다. 본인은 하다 보니 헷갈려서 이렇게 정의하고 구현하였다.

 

• 카드를 받을 때, 앞쪽(Front)
• 카드를 사용할 때, 앞쪽(Front)
• 그라운드에 내려놓을 때, 뒤쪽(Rear)
• 그라운드를 합칠 때, 카드 뒤쪽(Rear) , 그라운드 앞쪽(Front)

 이 정도만 정의하고 구현한다면, 어렵지 않게 구현할 수 있다. 

 

p.s 문제의 설명이 좀 난해한데, 도도가 먼저 카드를 내려놓았다면, 그것이 1번이다. 그다음  수연이가 카드를 내려놓는 것은 2번째 게임의 행위임을 인지하자.(이것 때문에 결과가 안 나와 엄청 헤매었다.. -_-;)

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        Main test = new Main();
    }

    public Main() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine()," ");

        int card_cnt = Integer.parseInt(stk.nextToken());
        int game_cnt = Integer.parseInt(stk.nextToken());

        Deque<Integer> do_cards = new LinkedList<>();
        Deque<Integer> su_cards = new LinkedList<>();

        //입력
        for (int i = 0 ; i < card_cnt ; i++){
            stk = new StringTokenizer(br.readLine()," ");
            do_cards.addFirst(Integer.parseInt(stk.nextToken()));
            su_cards.addFirst(Integer.parseInt(stk.nextToken()));
        }

        System.out.println(solution(do_cards,su_cards,game_cnt));

    }

    private String solution(Deque<Integer> do_cards, Deque<Integer> su_cards, int game_cnt) {
        //결과 반환용
        String result ;
        //중도 게임 오버 체크
        boolean gameover = false;

        Deque<Integer> do_ground = new LinkedList<>();
        Deque<Integer> su_ground = new LinkedList<>();

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

            //한쪽이라도 카드가 비었다면 gameover 
            if(do_cards.isEmpty() || su_cards.isEmpty()){
                gameover =true;
                break;
            }
            int cur_do;
            int cur_su;
            //스택의 형태로 빼옴
            if( i %2 ==0){
                cur_do = do_cards.pollFirst();

                do_ground.addLast(cur_do);
                if(do_cards.isEmpty()){
                    gameover =true;
                    break;
                }

                cur_su  = (su_ground.isEmpty()) ? 0 : su_ground.peekLast();
                if(cur_do ==5 || cur_su ==5){
                    //do win case
                    while(!su_ground.isEmpty()){
                        do_cards.addLast(su_ground.pollFirst());
                    }
                    while(!do_ground.isEmpty()){
                        do_cards.addLast(do_ground.pollFirst());
                    }

                }else if(cur_do+cur_su ==5){
                    //su win case
                    while(!do_ground.isEmpty()){
                        su_cards.addLast(do_ground.pollFirst());
                    }
                    while(!su_ground.isEmpty()){
                        su_cards.addLast(su_ground.pollFirst());
                    }
                }else{
                    //no one win



                }



            }else{
                cur_su = su_cards.pollFirst();
                su_ground.addLast(cur_su);
                if(do_cards.isEmpty()){
                    gameover =true;
                    break;
                }
                cur_do = (do_ground.isEmpty()) ? 0 : do_ground.peekLast();
                if(cur_do ==5 || cur_su ==5){
                    //do win case
                    while(!su_ground.isEmpty()){
                        do_cards.addLast(su_ground.pollFirst());
                    }
                    while(!do_ground.isEmpty()){
                        do_cards.addLast(do_ground.pollFirst());
                    }

                }else if(cur_do+cur_su ==5){
                    //su win case
                    while(!do_ground.isEmpty()){
                        su_cards.addLast(do_ground.pollFirst());
                    }
                    while(!su_ground.isEmpty()){
                        su_cards.addLast(su_ground.pollFirst());
                    }
                }else{
                    //no one win

                }

            }

        }


        //중간에 게임이 끝난 경우
        if(gameover){
            if(do_cards.isEmpty()){
                result = "su";
            }else{
                result = "do";
            }
        }else{
            //모든 게임 횟수가 끝나도 승부가 나지 않았다면,
            if(do_cards.size() > su_cards.size()){
                result = "do";
            }else if (do_cards.size() < su_cards.size()){
                result = "su";
            }else{
                result = "dosu";
            }

        }

        return result;
    }
}

결과

 디큐를 활용할 수 있는 좋은 문제였다. 다만, 처음 설계 시, 문제를 잘못 읽어서, do와 su가 한 번씩 내려놓는 경우를 1번이라고 정의했다가 고치는 과정에서 코드가 너무 조잡해졌다. (-_-;) do와 su를 배열로 사용했다면, 코드를 대폭 줄일 수 있었는데, 아쉽다. 

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.