프로그래머스 크레인 인형뽑기 - 자바(java) stack

 

2차원 배열이 정사각형으로 주어지고, moves에 x좌표로 크레인을 떨궈 인형 뽑기를 한다. 이후 담아두는데 같은 인형이면 터뜨리면서 값을 +2 해주는 문제이다.

 

터뜨려지는 수만 구하면 되는 문제라 쉽게 생각해봤다.

먼저 위에서 인형이 있는 위치까지 내려와야 하므로 board[i][moves[j]-1] 가 0이 아니라면 인형이 있는 것으로 판단했다.

스택을 선언하고 기존 0을 넣은 후 비교해서 같다면 pop 하고, answer +2를 해주었다.

 

 

import java.util.*;
class Solution {
    public int solution(int[][] board, int[] moves) {
        int answer = 0;
        Stack<Integer> crain = new Stack<>();
        crain.push(0); //비교를 위해 0 삽입
        int k = 0;
        
        for(int i = 0; i < moves.length; i++){      // 문제 반복
            for(int j  = 0; j < board.length; j++){ // 세로 반복
                if(board[j][moves[i]-1] != 0){        // 맨위를 잡았을 때
                    if(crain.peek() == board[j][moves[i]-1] ){ // 스택 top과 비교
                        crain.pop();
                        answer += 2;
                    }else{
                        crain.push(board[j][moves[i]-1]); // 같지 않다면 스택에 삽입
                    }
                    board[j][moves[i]-1] = 0;             // 뽑은 위치는 0으로 설정
                    break;
                }
            }
        }
        return answer;
    }
}

 

스택 구조를 2학년,,? 공부한 이후로 코드로는 처음 사용해서 간단히 정리하려 한다.

 

 - 스택

 

후입선출 의 구조로 LIFO( Last In First Out ) 구조이다. 

맨 위에서만 제거나 추가 연산이 이뤄진다.

 

- 메서드 정리

 

push(element): 스택의 맨 위에 요소를 추가합니다.

pop(): 스택의 맨 위에 있는 요소를 제거하고 반환합니다. 스택이 비어 있으면 EmptyStackException이 발생합니다.

peek(): 스택의 맨 위에 있는 요소를 제거하지 않고 반환합니다. 스택이 비어 있으면 EmptyStackException이 발생합니다.

empty():  스택이 비어 있는지 확인합니다. 스택이 비어 있으면 'true'를 반환합니다. 그렇지 않으면 'false'를 반환합니다.

search(element): 스택에서 지정된 요소를 검색하고 그 위치를 상단으로부터의 오프셋으로 반환합니다. 최상위 요소는 위치 1에 있는 것으로 간주됩니다. 요소를 찾을 수 없으면 -1을 반환합니다.

 

사용 예제

 

import java.util.Stack;
 
public class StackExample {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
 
        stack.push(10);
        stack.push(20);
        stack.push(30);
 
        System.out.println("스택: " + stack);
 
        int top = stack.pop();
        System.out.println("Pop된 요소: " + top);
        System.out.println("Pop 사용 후: " + stack);
 
        int peekedElement = stack.peek();
        System.out.println("Peek 요소: " + peekedElement);
        System.out.println("Peek 사용 시: " + stack);
 
        boolean isEmpty = stack.empty();
        System.out.println("스택이 비어있는가? " + isEmpty);
 
        int position = stack.search(20);
        System.out.println("20의 위치: " + position);
    }
}
 

 

스택: [10, 20, 30]
Pop된 요소: 30
Pop 사용 후: [10, 20]
Peek 요소: 20
Peek 사용 시: [10, 20]
스택이 비어있는가? false
20의 위치: 2

 

 

Stack 자료구조는 다양한 이유로 사용되어지며, 흔히 사용하는 예제는 이렇다.

 

• 괄호 검사 - 소, 중, 대괄호의 짝검사에 사용
• 임시 데이터 저장 - ctrl+c ctrl+v처럼
• 역순처리 - 데이터를 역으로 처리할 때 사용
• 후위 표기법 계산 - 연산자를 피 연산자 뒤에 배치하여 수식을 표현할 때
• undo기능 - 뒤로 가기와 앞으로 이동 기능을 구현하기 용이