알고리즘 풀이 - 프로그래머스(크레인 인형뽑기(Lv 1), 스택)

 

관련글

 

스택 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

크레인에서 인형을 뽑는 방법이 주어질 때, 같은 인형이 인접 시, 터뜨려지는데 그 인형의 수를 구하는 문제

(난이도 1)

 

 

2. 풀이

 

단순한 Stack 문제이다. 마지막에 우측에 넣은 인형이 무엇인지 확인하고, 현재 넣을 인형과 비교해 터뜨릴 지, 아니면 바로 넣을지를 찾아 푸는 문제이다.

간단한 문제이므로 코드를 통해 알아보자.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

import java.util.Arrays;
import java.util.LinkedList;
class Solution {
    public int solution(int[][] board, int[] moves) {
        int answer = 0;
        
        LinkedList<Integer> list = new LinkedList<>();
        for(int i=0; i < moves.length; i++){
            // 어떤 열에서 뽑을 차례인지 확인(index이므로 1뺀다.)
            int column = moves[i]-1;
            
            // 0이 아닌 경우가 인형이므로 0이 아닌 것을 찾을 때까지 반복
            for(int j=0; j < board.length; j++){
                if(board[j][column] > 0) {
                    int num = board[j][column];
                    board[j][column] = 0;
                    
                    // 기존에 넣은 인형이 1개 이상이고 마지막에 넣은게 같은 인형이면
                    if(!list.isEmpty() && list.getLast() == num){
                    
                        // 터뜨린 숫자를 2더하고 마지막에 넣은 것을 뺀다.
                        answer += 2;
                        list.pollLast();
                    } else {
                    
                        // 현재 인형을 넣는다.
                        list.add(num);
                    }
                    // 인형 작업이 끝났으니 더 이상 반복문을 돌지 않도록 break
                    break;
                }
            }
        }
        
        return answer;
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.