240301 TIL - 프로그래머스 크레인 인형뽑기

오늘은 프로그래머스 크레인 인형뽑기 문제를 풀었다.

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

 

문제

이 문제는 n*n 2차원 배열을 한곳에 쌓고 같은 숫자가 들어오면 같은 쌓은 곳에서 둘다 제거를 해서 몇 개의 숫자가 사라졌는지 구하는 문제이다.

접근

먼저 쌓는다는 개념으로 접근했기 때문에 Stack자료구조를 사용해서 풀이를 하였다.

숫자를 가져올 곳을 정하는 moves배열을 돌면서 2차원 배열에서 해당하는 숫자를 가져와야하기 떄문에 이중 for문을 사용해서 문제를 풀이 하였다.

코드

import java.util.*;

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

풀이

먼저 뽑은 숫자를 쌓을 Stack<Integer> stk 를 선언 하고, moves배열은 0번 index가 1로 표현되므로 for문 안에서 각각 원소인 n을 하나씩줄여주고 두 번째 for문 안에 arr[n]이 0이 아닌 경우에 뽑는 것이므로 arr[n] ! = 0 일 경우에 각각 상황에 맞게 로직을 설정해주었다.

먼저 쌓아놓은것이 없을 때는 Stack에 arr[n]을 push 해주고 쌓은 숫자가 Stack에 가장 위쪽의 숫자와 일치한다면 쌓지 말고 쌓아놓은 것을 없애기 위해 stk.pop()을 해주고 2개가 사라졌으므로 answer에 2를 추가해준다 또 Stack이 비어있지않고 Stack에 가장 위 숫자가 쌓을 숫자와 다를 경우 없애지말고 그대로 쌓으므로 stk.push(arr[n]) 을 통해 쌓아준다 이렇게 뽑은 숫자를 처리해주면 그 자리는 공석이 되므로 arr[n] = 0 으로 재정의 해주고 두 번째 반복문을 break로 멈춰주고 moves배열의 다음 원소로 넘어가는 식으로 해결해주었다.

 

 

레벨이 오를수록 예전에는 배열로 해결했던 문제들이 점점 Stack, Queue등 다양한 자료구조를 활용하는 식으로 요구를 하고 풀이를 하는 것같다. 이런 문제를 해결할 수록 다양한 자료구조에 대한 활용에 점점 익숙해지는 것 같다. 오늘 풀어봤던 문제중에 dfs, 재귀를 사용하는 문제도 보았는데 이부분은 아직 더 생소해서 코드에 대한 이해만 대략적으로 하고 다음에 다시 풀어보기로 했다. 점점 문제들이 어려워지고 다양한 알고리즘에 대해 이해도 필요해지는 것 같다. 지금까지 단순 구현만으로는 앞으로 문제들을 풀기 쉽지 않을 것 같고 이론에 대한 공부도 병행을 해야 할 것 같다.