📑 1. 문제설명





💡 2. 풀이 과정
문제 예시처럼 5*5 격자가 있다고 가정 해 보면 격자의 가장 아래 칸부터 인형이 차곡차곡 쌓여 있고, 가장 위에 있는 인형을 집어 올릴 수 있다. 이 문제에서 "집어 올린 인형은 바구니에 쌓이는데 바구니의 가장 아래 칸부터 인형이 순서대로 쌓인다."라는 부분을 보면 스택 문제인 걸 바로 알 수 있다.
게임화면이나 바구니를 스택이라고 생각하면 된다. 문제는 board 배열을 스택으로 변환시키는 것이 어렵다. 만약에 값이 0이 들어오면 빈 칸이기 때문에 스택에 넣지 않는다. 그리고 크레인이 인형을 꺼내는 것은 stack.pop()으로 구현할 수 있다.
인형뽑기 게임 로직
1. 바구니가 빈 경우 -> 무조건 푸시
2. 바구니가 비지 않은 경우
2-1. 바구니의 가장 위에 있는 인형과 지금 넣으려는 인형이 같은가?
2-1-1. 같다 → stack.pop() 후 사라진 인형은 2개이다. 따라서 answer+=2;
2-2-2. 다르다 → stack.push() 스택에 인형을 넣는다.
3. return answer
예시 배열 그림으로 보기


아직 크레인이 동작하지 않은 초기 상태는 위와 같다.
여기서 [1, 5, 3, 5, 1, 2, 1, 4] 순서로 크레인을 움직여 인형을 뽑는다.
1. 첫 번째 시도 (1)
[1, 5, 3, 5, 1, 2, 1, 4]

바구니가 비었기 때문에 크레인이 첫번째 스택에서 인형4를 집어서 바구니에 푸시한다.
2. 두 번째 시도 (5)
[5, 3, 5, 1, 2, 1, 4]

5번째 스택에서 인형 3을 집어서 바구니에 푸시한다. 이 때부터는 가장 최근에 푸시한 인형과 숫자를 비교해서 같은 인형이면 둘다 제거한다. 3 != 4이므로 그대로 푸시한다.
3. 세 번째 시도 (3)
[3, 5, 1, 2, 1, 4]

스택 3에서 인형1을 집어서 바구니에 넣는다. 바구니 맨 위의 인형과 값이 다르므로 그대로 둔다 (1 != 3)
4. 네 번째 시도 (5)
[5, 1, 2, 1, 4]


스택5에서 인형을 집어 옮기며 같은 작업을 한다. 바구니 맨 위의 인형과 옮긴 인형이 1번으로 같기 때문에 바구니 안의 인형을 팝한다. 그리고 스택5에서 집은 인형도 사라지므로 2개의 인형이 사라진다. 그래서 없어진 인형을 뜻하는 변수 answer에는 2개의 카운트가 올라가게 된다.
5. 다섯 번째 시도 (1)
[1, 2, 1, 4]


또 스택 1에서 인형 3을 집어서 바구니로 옮긴다. 이 때도 바구니 맨 위의 인형이 3번으로 번호가 같기 때문에 팝하고, 집은 인형도 지운다. 없어진 인형 +2를 해서 4가 된다.
6. 여섯 번째 시도 (2)
[2, 1, 4]

두 번째 스택에서 인형 2를 바구니로 옮긴다.
7. 일곱 번째 시도 (1)
[1, 4]
첫 번째 스택에는 인형이 하나도 없기 때문에 아무 동작도 일어나지 않는다.
8. 여덟 번째 시도 (4)
[4]

마지막으로 4번째 스택에서 인형 4를 뽑아서 바구니에 옮긴다. 직전에 바구니에 들어온 인형과 비교했지만 인형의 숫자가 동일하지 않아서 그대로 푸시한다. (4 != 2)

문제에서 주어진 예시 배열대로 인형을 뽑은 후 최종 화면의 모습은 위와 같다.
⭐ 3. 정답코드
public int solution(int[][] board, int[] moves) {
int answer = 0; // 터진 인형의 총 개수 (2개씩 사라짐)
Stack<Integer> stack = new Stack<>(); // 뽑은 인형을 저장할 스택
// 'moves' 배열의 각 이동에 대해 반복
for (int move : moves) {
// 각 열을 순차적으로 확인 (board.length는 행의 개수)
for (int j = 0; j < board.length; j++) {
// 현재 위치에 인형이 있다면 (0이 아닌 값)
if (board[j][move - 1] != 0) {
int doll = board[j][move - 1]; // 해당 위치의 인형을 가져옴
// 스택이 비어있지 않고, 스택의 맨 위 인형과 현재 인형이 같으면
if (!stack.isEmpty() && stack.peek() == doll) {
stack.pop(); // 인형을 터뜨리기 위해 스택에서 제거
answer += 2; // 같은 인형이 터져서 2개가 사라짐
} else {
stack.push(doll); // 스택에 인형을 추가
}
board[j][move - 1] = 0; // 뽑은 인형은 해당 위치에서 제거 (0으로 설정)
break; // 한 번에 하나의 인형만 뽑을 수 있으므로 반복문을 탈출
}
}
}
return answer; // 터진 인형의 총 개수 반환
}
자꾸 런타임 오류가 나서 몇 번 고쳤다. IndexOutOfBoundsException이나 NullPointerException에 주의해야 한다.
특히 board의 열 인덱스와 move 배열을 처리하는 부분에서 인덱스에 신경써야 한다.
⭐ board[j][move - 1] != 0에서 move - 1을 사용하는 이유
인덱스가 0부터 시작하기 때문이다.
현재 moves 배열에는 각 열에서 인형을 뽑는 순서가 들어있는데, 예를 들어, moves = [1, 5, 3, 2]라면 첫 번째, 다섯 번째, 세 번째, 두 번째 열에서 인형을 뽑겠다는 의미이다.
하지만 자바에서 배열 인덱스는 0부터 시작하기 때문에, move 값이 1일 때는 board 배열에서 0번째 열을 참조해야 한다. 그래서 따라서 move - 1을 사용하여 1이 들어있는 moves 배열 값을1-based 에서 0-based 인덱스로 변환해 주는 것이다.
⭐여기서 !stack.isEmpty()를 하는 이유
if (!stack.isEmpty() && stack.peek() == doll) {
stack.pop();
answer += 2; // 같은 인형이 겹쳐서 터지면 2개가 사라짐
}
스택이 비어있을 때 peek()을 호출하면 EmptyStackException 예외가 발생하기 때문이다.
이걸 방지하려면 !stack.isEmpty()를 하거나 stack.push(0);로 더미 값(0)을 추가해야 한다.처음부터 0을 넣어두면, stack.peek()를 호출할 때 항상 비교할 값이 존재한다.
Stack<Integer> stack = new Stack<>();
System.out.println(stack.peek()); // java.util.EmptyStackException 발생!
'코딩테스트 > JAVA테스트' 카테고리의 다른 글
| [백준] (Java) 요세푸스 문제 (큐) (7) | 2025.02.20 |
|---|---|
| [프로그래머스] (Java) 예상대진표 (트리) (13) | 2025.02.20 |
| [코딩테스트] (Java) 십진수를 이진수로 변환하기 (스택) (17) | 2025.02.17 |
| [프로그래머스] (Java / 자바 ) 유연근무제 문제풀이 (11) | 2025.02.14 |
| [프로그래머스] (Java) 오픈채팅방 문제풀이 (2) | 2025.02.11 |