[코딩테스트] 크레인 인형뽑기 게임, Stack | 프로그래머스

Bluewave·2024년 5월 29일

코테공부_java

목록 보기

34/99

문제

문제	레벨	정답률
크레인 인형뽑기 게임	Lv.1	52%

My Code

import java.util.*;

class Solution {
    public int solution(int[][] board, int[] moves) {
        Stack<Integer> basket = new Stack<>();
        int result = 0;
        
        for(int i = 0; i<moves.length; i++){
            int move = moves[i];
            int depth = 0;
            int item = 0;
            
            item = board[depth][move-1];
            while(item == 0 && depth<board.length-1){
                depth++;
                item = board[depth][move-1];
            }
            
            if(item == 0){
                continue;
            } else{
                board[depth][move-1] = 0;
            }

            if(!basket.empty() && basket.peek() == item){
                basket.pop();
                result+=2;
            } else{
                basket.push(item);
            }
        }
        
        return result;
    }
}

나는 문제를 읽자마자 LIFO 자료구조를 활용해야겠다는 생각이 먼저 들었다. 그래서 사용한 것이 Stack.
사실 Stack를 활용하여 코드를 짜본게 처음인데, 점차 응용력이 늘고 있다는 느낌이 들어서 기분이 좋았다.

moves.length만큼 돌면서 board에서 moves[i] 위치의 item을 찾는다.
만약 0이고 depth 값이 board 길이보다 작다면 depth를 1 증가시키며 0이 아닌 숫자가 나올때까지 아래로 계속 찾아 나간다.
item을 찾고 나서, 0이라면 그 칸에 인형이 없는 상황이니 다음으로 넘어가고, 아니라면 찾은 board 위치의 값을 0으로 만든다.
basket이 비어있지 않고, basket의 가장 위의 아이템이 현재 아이템과 값이 일치한다면 basket.pop()해서 없애고 result를 2 증가시킨다.
그게 아닌 경우엔 basket에 값을 넣어준다.

사실 처음에는 오류가 났다. 이유가 뭐지... 살펴보니 바로 result를 1 증가시켰던 것.. 터지는 상황이 몇 번인지를 세는게 아니라, 터지는 인형이 몇 개인지를 세는 것이기 때문에 2를 증가시켜야했다.

최적화 코드

import java.util.*;

class Solution {
    public int solution(int[][] board, int[] moves) {
        Stack<Integer> basket = new Stack<>();
        int result = 0;

        for (int move : moves) {
            int column = move - 1;

            // Find the first non-zero item in the column
            int item = 0;
            for (int row = 0; row < board.length; row++) {
                if (board[row][column] != 0) {
                    item = board[row][column];
                    board[row][column] = 0;
                    break;
                }
            }

            // If no item was found, continue to the next move
            if (item == 0) {
                continue;
            }

            // Check the basket for the same item on top
            if (!basket.isEmpty() && basket.peek() == item) {
                basket.pop();
                result += 2; // Two items are removed
            } else {
                basket.push(item);
            }
        }

        return result;
    }
}

개선점

불필요한 변수 초기화 없앰
while 루프 간결하게 수정
for 루프를 enhanced for loop로 변경 -> 가독성 up!

사실 이번 코드 최적화는 엄청 크게 달라진 점은 없지만, 정석 for루프를 사용할 필요가 없는 코드였다. i를 쓸 일이 없기 때문,,

약간 이거 보고 "스티커를 붙이는 센스가 인생의 센스이기도 하다"라는 대사가 생각났다. 코딩으로 치면..
"코드를 짜는 센스가 인생의 센스이기도 하다" 요런 느낌이랄까 ㅋㅎ

Stack

아무래도 Stack을 처음 써봐서 제대로 짚고 넘어갈 필요가 있다고 생각해서 정리해봤다.

스택은 자료구조의 한 종류로, LIFO 방식을 따른다.

주요 연산

삽입 Push
삭제 Pop
조회 Peek or Top
비어 있는지 확인 isEmpty

Java에서는 java.util.Stack 클래스를 사용하여 쉽게 구현 가능!

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();

        // 삽입 (push)
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println("Stack after pushes: " + stack);

        // 삭제 (pop)
        int poppedElement = stack.pop();
        System.out.println("Popped element: " + poppedElement);
        System.out.println("Stack after pop: " + stack);

        // 조회 (peek)
        int topElement = stack.peek();
        System.out.println("Top element: " + topElement);
        System.out.println("Stack after peek: " + stack);

        // 스택이 비었는지 확인 (empty)
        boolean isEmpty = stack.isEmpty();
        System.out.println("Is stack empty? " + isEmpty);
    }
}