프로그래머스(Java)-크레인 인형뽑기 연습

민지킴·2021년 3월 8일
0

프로그래머스

목록 보기
1/42
post-thumbnail

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/64061

문제 풀이

값들이 쌓이는 부분(바구니)을 맨 처음 배열로 구현하고, 모든 값들이 쌓이고나서 같은 값들이 인접할 경우 제거 되는 logic을 구현했는데 잘 풀리지 않았다. 고민해보니 바구니에서 궁금한 값은 가장 최근에 들어간 마지막 값이고 이 값을 효과적으로 다루는 stack을 통해서 구현해보자는 생각이 들었다.

 Stack<Integer>res = new Stack();

또한 각 line에서 제일 높은 부분을 height 배열을 만들어서
가장 먼저 값이 나오는 지점을 높이로 설정했다.
ex) 5x5크기에서 index가 1에서 최초로 값이 등장했다면.
높이 = 5 - 1 =4 가 된다.

int  [] height = new int[board.length];
        Arrays.fill(height,0);
        for(int i=0; i<board.length;i++){
            for(int j=0; j<board[i].length; j++){
                if(board[i][j]!=0 && height[j]==0){
                    height[j]=board.length-i;
                }
            }
        }

해당 line의 높이가 0인경우에는 그 line에는 더이상 인형이 없으므로 continue

바구니에 값이 없는 경우(res.size()==0) 에는 무조건 stack에 값을 추가

아닌 경우에는 가장 위에값과, 지금 추가하려는 값이 같은경우에는 가장 위에있는 값을 pop시키고 아닌경우에는 push한다.

for(int i=0; i<moves.length; i++){
            if(height[moves[i]-1]==0){
                continue;
            }
            
            if(board[board.length-height[moves[i]-1]][moves[i]-1]!=0){
                if(res.size()==0){
                     res.push(board[board.length-height[moves[i]-1]][moves[i]-1]);
                    
                }else{
                    if(res.peek()==board[board.length-height[moves[i]-1]][moves[i]-1]){
                        res.pop();
                        answer+=2;
                    }else{
                        res.push(board[board.length-height[moves[i]-1]][moves[i]-1]);
                    }
                }
                 height[moves[i]-1]--;

            }
        }

코드

import java.util.*;

class Solution {
    public int solution(int[][] board, int[] moves) {
        int answer = 0;
        Stack<Integer>res = new Stack();
        
        int  [] height = new int[board.length];
        Arrays.fill(height,0);
        for(int i=0; i<board.length;i++){
            for(int j=0; j<board[i].length; j++){
                if(board[i][j]!=0 && height[j]==0){
                    height[j]=board.length-i;
                }
            }
        }
        //System.out.println(Arrays.toString(height));
        
        
        for(int i=0; i<moves.length; i++){
            if(height[moves[i]-1]==0){
                continue;
            }
            
            if(board[board.length-height[moves[i]-1]][moves[i]-1]!=0){
                if(res.size()==0){
                     res.push(board[board.length-height[moves[i]-1]][moves[i]-1]);
                    
                }else{
                    if(res.peek()==board[board.length-height[moves[i]-1]][moves[i]-1]){
                        res.pop();
                        answer+=2;
                    }else{
                        res.push(board[board.length-height[moves[i]-1]][moves[i]-1]);
                    }
                }
                 height[moves[i]-1]--;

            }
        }
        //System.out.println(res.toString());
        return answer;
    }
}
profile
하루하루는 성실하게 인생 전체는 되는대로

0개의 댓글