[프로그래머스] 2019 카카오 개발자 겨울 인턴십 - 크레인 인형뽑기 게임

2019 카카오 개발자 겨울 인턴십 - 크레인 인형뽑기 게임

---

< 문제 정의 >

---

< 문제 접근 >

위 문제의 입출력 예시와 그림을 대조해 보면,  N*N 크기의 격자형 인형통은 가장 위에서부터 정수형 2차원 배열로 이루어 져 있으며, 같은 정수는 같은 종류의 인형이라는 것을 알 수 있다. 또한 moves배열은 크레인의 움직임을 의미하며, 예시처럼 인형 통의 크기가 5*5일 경우, 1열부터 5열까지 크레인을 움직이는 명령을 순차적으로 저장한 배열이며, N*N크기 인형통에서 N이하의 수만 원소로 가질 수 있다.

 

이 문제에서 사용해야 할 자료구조는, 인형통에서 뽑인 인형이 뽑힌 후에 이동하는 저장공간(이하 바구니)에 맨 아래부터 위로 하나씩 차곡차곡 쌓이는 구조이며, 새로운 인형이 들어오는 순간, 이전에 저장되어 있던 인형과 같으면 두 개의 인형을 바구니에서 삭제(Pop) 해야 하기 때문에, '스택' 을 사용해야 함을 알 수 있다.

 

---

< 문제 해결 >

public static int solution(int[][] board, int[] moves) {
        int answer = 0;
        Stack<Integer> st = new Stack<Integer>();

        for(int i=0; i<moves.length; i++) { // ## 반복1 : 크레인의 이동 위치.
            for(int j=0; j<board.length; j++) { // ## 반복2 : 크레인이 내려갈 열에 있는 인형들.
                int target = moves[i]-1; // 크레인을 내릴 '열'의 index
                int doll = board[j][target]; // 현재 열에서 포커싱된 인형

                if(doll != 0) { // 인형이 존재 할 경우만 실행.
                    if(st.isEmpty()) {
                        st.push(doll); // 스택이 비어있으면 무조건 넣는다.
                    }
                    else { // 스택이 비어있지 않고,
                        if(st.peek() == doll) { // 스택의 최상위에 있는 요소가 현재 doll과 같을 경우
                            st.pop(); // 스택에서 해당 인형을 빼 내고
                            answer += 2; // 인형이 2개 없어졌으므로 2를 증가시킨다.
                        }
                        else { // 스택의 최상위 요소가 현재 doll과 같이 않을 경우.
                            st.push(doll); // 스택에 push한다.
                        }
                    }
                    board[j][target] = 0; // 위 작업이 끝나면 원본 배열에서 해당 인형을 0으로 바꿔준다.
                    break; // 해당 열의 맨 위에 있는 인형을 뽑았으므로 끝까지 진행 불필요. '반복2' 종료.
                }
            }
        }
        return answer;
    }

가장 먼저, 핵심 자료구조는 '스택' 이기 때문에 정수 자료형을 저장할 스택 st 를 선언해 주도록 한다.

'인형을 뽑은 행위' 는 moves 배열의 길이만큼 수행되기 때문에 첫 번 째 for문은 moves 배열의 길이만큼 수행한다.

다음으로 인형을 뽑기 위해 크레인을 내릴 위치는 moves 배열을 통하여 알 수 있는데, 인형통 2차원 배열의 index는 0부터 시작하기 때문에, moves 배열의 값에서 -1 을 해준 값이 인형통에서 크레인을 내릴 '열'의 위치를 의미한다.

 

포커싱 된 인형, 즉, 뽑히게 될 인형은 board[ 행(맨 위에서 부터 아래로) ][ 크레인이 위치한 index ] 가 된다. 해당 인형이 몇 번 인형인지를 'doll'에 저장한다.

 

다음으로 doll이 0일 경우에는 해당 위치에 인형이 없다는 의미이므로 아무것도 수행하지 않는다. 반대로 현재 '열' 에서 위에서부터 아래로 내려가면서 0이 아닌 수가 나올 경우(인형이 존재 할 경우) 인형을 뽑는 action을 수행한다.

 

st.isEmpty() 로 스택을 검사하여, 스택이 비어있을 경우에는 st.push() 함수를 사용하여 스택에 doll을 넣는다(인형통에서 인형을 뽑아 바구니에 넣는다.)

 

만약 스택이 비어있지 않을 경우, 현재 스택의 최상위에 있는 값이 무엇인지 알기 위해 st.peek() 함수를 사용하여 해당 값이 현재 뽑으려고 하는 doll 과 같을 경우 스택에서 해당 인형을 st.pop() 하여 삭제하고, 직전에 넣으려던 doll과 스택에서 pop된 인형까지 총 2개가 사라지기 때문에 answer를 2 증가시킨다. 만약 넣으려는 doll과 스택 최상위에 있는 인형이 같지 않으면 st.push()로 스택에 새로운 인형을 쌓아준다.

 

인형을 뽑는 action이 끝나면,  인형통에서 해당 인형을 0으로 바꿔주고, 반복문을 break 한다. (이미 인형통에서 해당 열의 가장 위에 있는 인형을 뽑았기 때문에, 해당 열의 가장 아래 까지 내려 갈 필요가 없다.)

 

---

< 핵심 개념 >

Stack : 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO형 자료구조. 마지막의 데이터의 위치에 대해 삽입이나 삭제가 발생하는 경우 사용이 적합하다.

Stack<자료형> st = new Stack<자료형>(); // Stack 선언

st.push(원소); // Stack 최상위에 원소 삽입.

st.pop(); // Stack 최상위의 원소 삭제

st.peek(); // Stack 최상위의 원소 검사.

st.isEmpty(); // Stack이 비어있는지 여부 검사 (True / False)