[프로그래머스]크레인 인형 뽑기

4085 단어 알고리즘JavaJava

1. 문제

문제 설명

2019 카카오 개발자 겨울 인턴십에 나왔던 문제다. 보드판에 인형이 초기화되어 있고 크레인으로 인형을 건저서 다른 곳에 저장해둔다. 저장해둔 인형 중 2개 이상이 모였을 때 인형이 터지면서 터진 인형의 갯수를 return한다.
자세한 설명은 링크로 첨부한다.

제한 사항

  • board 배열은 2차원 배열로 크기는 5 x 5 이상 30 x 30 이하입니다.
  • board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다.
  • 0은 빈 칸을 나타냅니다.
  • 1 ~ 100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나타냅니다.
  • moves 배열의 크기는 1 이상 1,000 이하입니다.
  • moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.

입출력 예

boardmovesreturn
[[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]][1,5,3,5,1,2,1,4]4

2. 아이디어

  • 크레인으로 건져올려진 인형들이 저장되는 리스트를 만든다.
    리스트를 사용하는 이유 : 편하다. 요소를 삭제하면 그 사이즈도 줄어들어 삭제와 삽입에 수월하다.
  • moves의 각 요소에 -1을 해주어서 board[][]배열에 접근해야한다.
  • 2중 for문으로 배열 board의 각 요소에 접근하고 0이 아니면 꺼낸다. 꺼내고 난 후에 해당 인덱스의 값은 0으로 바꾸어준다.
  • 모은 인형의 갯수가 2개 이상일 때에 같은 인형이 연속되서 모여있는지 검사하고, 만약 그렇다면 해당 아이템을 리스트에서 삭제한 다음, answer에 2를 더한다.이거때문에 다 해놓고 좀 해맸다

3. 코드

public class KakaoCrain {
    public static  int solution(int[][] board, int[] moves) {
        int answer = 0;
        List<Integer>store = new ArrayList<>();//크레인으로 건져올린 인형들이 저장되는 배열
        //moves[i]의 값에 해당하는 board[*][i]를 찾아서 그 값을 store에 저장한다.
        for(int i = 0 ; i < moves.length;i++){
            int col = moves[i]-1;
            for(int j = 0; j < board[col].length; j++){
                if(board[j][col]!=0){
                    store.add(board[j][col]);
                    board[j][col] = 0;
                    break;
                }
            }
            //store[]에 같은 것이 두번연속해서 쌓이면 PANG
            if(store.size() >= 2) {
                if (store.get(store.size()-2) == store.get(store.size()-1)) {
                    store.remove(store.size()-1);
                    store.remove(store.size()-1);
                    answer+=2;
                }
            }

        }
        return answer;
    }

    public static void main(String[] args) {
        int[][] b = {{0,0,0,0,0},{0,0,1,0,3},{0,2,5,0,1},{4,2,4,4,2},{3,5,1,3,1}};
        int[] m = {1,5,3,5,1,2,1,4};


        System.out.println(solution(b, m));
    }
}

처음 문제를 봤을 때 스택으로 풀면 되겠다 싶었는데, 내가 스택에 익숙하지 않아서 리스트로 풀었다.
문제를 풀고 난 후, 다른 분들의 풀이를 보던 중 스택으로 푼 분이 계셔서 그 분의 코드를 첨부한다.

class Solution {
    public int solution(int[][] board, int[] moves) {
        int answer = 0;
        Stack<Integer> stack = new Stack<>();
        for (int move : moves) {
            for (int j = 0; j < board.length; j++) {
                if (board[j][move - 1] != 0) {
                    if (stack.isEmpty()) {
                        stack.push(board[j][move - 1]);
                        board[j][move - 1] = 0;
                        break;
                    }
                    if (board[j][move - 1] == stack.peek()) {
                        stack.pop();
                        answer += 2;
                    } else
                        stack.push(board[j][move - 1]);
                    board[j][move - 1] = 0;
                    break;
                }
            }
        }
        return answer;
    }
}

스택을 사용할 때는 새로운 아이템을 스택에 넣기 전에 스택의 젤 위 요소와 비교한다.

4. end..

Level1의 쉬운 문제임에도 불구하고 한번에 코드를 써내려가지 못했다. 디버깅도 여러번 했었다...
문제를 잘 읽고, 내가 다음 코드를 써내려 갈 때 무슨 목적의 코드인지 주석을 달며 써내려가는 연습을 해야겠다.

좋은 웹페이지 즐겨찾기