[인프런 알고리즘] Chapter 5, 3번 문제(크레인 인형뽑기(카카오))

이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.

---

문제 설명

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class sec05_03 {
    public static int solution(int[][] board, int[] moves)
    {
        int count = 0;
        Stack<Integer> stack = new Stack<>();
        for(int i : moves)
        {
            for(int j = 0; j < board.length; ++j) //y축
            {
                if(board[j][i - 1] != 0)
                {
                    if((!stack.isEmpty()) && (stack.peek() == (board[j][i - 1])))
                    {
                        stack.pop();
                        count += 2;
                    }
                    else stack.push(board[j][i - 1]);

                    board[j][i - 1] = 0;
                    break;
                }
            }
        }

        return count;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        int[][] board = new int [N][N];
        for(int i = 0; i < N; ++i)
        {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; ++j) board[i][j] = Integer.parseInt(st.nextToken());
        }

        int M = Integer.parseInt(br.readLine());
        int[] moves = new int[M];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; ++i) moves[i] = Integer.parseInt(st.nextToken());

        System.out.println(solution(board, moves));
    }
}

 

설명

• for(int i : moves) 반복문을 통해 크레인이 moves 배열에 따라 지정된 열에서 인형을 집는 동작을 반복한다.
• for(int j = 0; j < board.length; ++j) 내부 반복문을 통해 해당 열의 각 행을 위에서부터 순차적으로 검사하여, 가장 위에 있는 인형(board[j][i - 1])을 찾는다.
• 인형을 찾으면
  스택이 비어 있지 않고, 스택의 맨 위에 있는 인형과 같은 종류라면, 스택에서 인형을 제거하고, count를 2 증가시킨다.
• 그렇지 않다면, 인형을 스택에 추가한다.
• 인형을 집어 올린 위치는 board[j][i - 1] = 0;을 통해 0으로 만들어 인형이 없음을 표시한다.
• 인형을 집었으면, 해당 열의 탐색을 중지하고 다음 moves로 넘어간다.