📎 링크
programmers.co.kr/learn/courses/30/lessons/64061
📝 문제 설명
"N x N" 크기의 정사각 격자에 인형이 들어있다.
크레인을 좌우로 이용하여 멈춘 위치에서 맨 위에 있는 인형을 집어올린다.
들어올린 인형을 바구니의 아래 칸부터 순서대로 쌓는다.
이때 같은 모양의 인형이 연속해서 쌓이는 경우, 두 인형을 터뜨린다.
터뜨려서 없앤 인형의 개수를 return 하는 solution 함수를 만들어라.
👩🏻💻 알고리즘 풀이 순서
Step 1.
바구니의 가장 마지막에 들어간 인형 두 개를 비교해야 하기에, stack 을 미리 생성했다.
push와 pop(마지막으로 넣은 원소를 불러오기 + 제거), peek(마지막으로 넣은 원소를 불러오기) 을 사용해 문제를 풀었다.
Step 2.
moves 길이만큼 for 문을 돌린다.
moves 각각의 원소의 값(=인형뽑기 상자의 해당 위치)에 가서 인형을 하나씩 뽑아야 하기 때문.
Step 3.
board 의 길이만큼 for 문을 돌린다.
인형뽑기 상자의 해당 라인의 가장 위에 있는 인형을 고르기 위해. 0이 아닐 때 가장 먼저 나오는 값(=인형)을 집어든다.
Step 4.
크게 2가지 케이스로 분류
1) 스택이 비어있지 않고 & 가장 마지막에 집어넣은 인형이 새롭게 뽑은 인형과 같은 종류인 경우
그 두개의 인형을 터뜨려서 없애버리기 + 터뜨린 개수만큼 answer 에 추가
(참고로, 스택이 비어있다면 2개의 인형을 비교할 수 없기에, 스택이 비어있지 않는 상황이 전제가 되어야 함)
2)
a. 스택이 비어있는 경우
b. 스택이 비어있지 않지만, 가장 마지막에 넣은 인형과 새롭게 뽑은 인형이 다른 인형일 경우
새롭게 뽑은 인형을 스택에 추가하기
Step 5.
뽑은 인형은 board(=인형뽑기 상자)에서 제거해야 하기에, 값을 0으로 덮어 씌운다.
import java.util.Stack;
class Solution {
public int solution(int[][] board, int[] moves) {
int answer = 0;
// Step 1
Stack<Integer> st = new Stack<>();
// Step 2
for (int i = 0; i < moves.length; i++) {
// Step 3
for (int j = 0; j < board.length; j++) {
if (board[j][moves[i] - 1] != 0) {
// Step 4
if (!st.isEmpty() && st.peek() == board[j][moves[i] - 1]) {
st.pop();
answer += 2;
} else {
st.push(board[j][moves[i] - 1]);
}
// Step 5
board[j][moves[i] - 1] = 0;
break;
}
}
}
return answer;
}
}