섹션 5. Stack, Queue(자료구조) 3. 크레인 인형뽑기(카카오)

문제

입력

• 첫 줄에 자연수 N(5<=N<=30)이 주어집니다.
• 두 번째 줄부터 N*N board 배열이 주어집니다.
• board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다.
• 0은 빈 칸을 나타냅니다.
• 1 ~ 100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나타냅니다.
• board배열이 끝난 다음줄에 moves 배열의 길이 M이 주어집니다.
• 마지막 줄에는 moves 배열이 주어집니다.
• moves 배열의 크기는 1 이상 1,000 이하입니다.
• moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.

출력

• 첫 줄에 터트려져 사라진 인형의 개수를 출력합니다.

입출력 예제

---

풀이방식

이번 문제는 Stack과 2차원 배열을 사용하여 푸는 문제이다.

---

설계과정

1. 인형(board)과 크레인(moves)을 입력받을 배열을 선언한다.

2. 크레인의 움직임을 배열의 행과 열로 제어한다.

3. board 배열에 값이 0이 아니면 인형을 꺼내고 해당 위치에 값을 0으로 바꾼다. 

4. 바구니(스택)에 인형이 있는 상태에서 동일한 인형이 들어오면 결과값에 2를 더하고 해당 인형들을 바구니에서 뺀다.

5. 동일하지 않으면 그대로 인형을 바구니에 넣는다.

---

풀이과정

1. 인형과 크레인을 입력받을 배열을 선언한다.

• board : 인형 배열
• moves : 크레인 배열

2. int 형으로 메소드를 작성한다.

 

3. 결과값을 출력할  result와 Stack을 선언한다.

 

4. moves 배열에 들어간 각 값들을 pos에 대입해서 for문을 돌린다.

• moves 배열에는 크레인이 이동하는 위치값들이 들어있다.
• pos 는 moves 배열에 각 값들을 매치한 값이다.

5. 0부터  배열 board의 길이만큼 도는 for문을 작성한다.

• board.length()는 배열의 길이를 나타내는 것으로, 2차원 배열의 행을 의미한다.

6. board[i][pos-1] 가 0이 아니면 해당 위치에 인형값을 임의의 변수 tmp에 저장하고, 값을 0으로 변경한다.

• pos -1 : 
• board[i][pos-1] 가 0이 아니라는 것은 인형이 있다는 의미이다.
• 인형을 꺼내고 나면 해당 위치가 비어있게 되므로 0으로 값을 변경한다.

7. 바구니(스택)에 인형이 있는 상태에서 새로 들어간 인형과 동일한지 확인한다.

• 기존에 있던 인형과 크레인으로 집은 인형이 동일한지 확인한다.
• isEmpty() : 값이 비었는지 확인하여 true / false로 리턴한다.
• peek() : 스택에서 가장 상단의 값을 리턴받는다. 단, pop()와 달리 값을 꺼내지 않고 단순히 읽는다.

8. 위의 식이 성립하면 두 개의 인형이 터져야하므로 result에 2를 더하고, 바구니에서 인형을 제거한다.

9. 바구니(스택)에 인형이 새로 들어간 인형과 다르다면 그대로 넣는다.

10. if 문을 돌아서 한 번 인형을 찾으면 또 다시 for문이 돌면 안되기 때문에 break로 빠져나온다.

 

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.