[문제풀이] 05-03 크레인 인형 뽑기(카카오)

2019 카카오 개발자 겨울 인턴십 문제,

인프런, 자바(Java) 알고리즘 문제풀이

Stack, Queue(자료구조) - 0503. 크레인 인형 뽑기

🗒️ 문제

🎈 나의 풀이

	private static int solution(List<Queue<Integer>> board, int[] moves) {
        int answer = 0;
        Stack<Integer> bucket = new Stack<>();

        for(int i : moves) {
            int doll = 0;

            if(!board.get(i-1).isEmpty()) {
                doll = board.get(i-1).poll();
            }

            if(doll != 0) {
                if(bucket.empty() || bucket.peek() != doll) bucket.push(doll);
                else {
                    bucket.pop();
                    answer += 2;
                }
            }
        }

        return answer;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        List<Queue<Integer>> board = new ArrayList<>();

        for(int i=0; i<n; i++) board.add(new LinkedList<>());

        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                int input = sc.nextInt();
                if(input !=0) {
                    board.get(j).add(input);
                }
            }
        }

        int m = sc.nextInt();
        int[] moves = new int[m];

        for(int i=0; i<m; i++) moves[i] = sc.nextInt();

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

🖍️ 강의 풀이

    public int solution(int[][] board, int[] moves){
		int answer=0;
		Stack<Integer> stack = new Stack<>();
		for(int pos : moves){
			for(int i=0; i<board.length; i++){
				if(board[i][pos-1]!=0){
					int tmp=board[i][pos-1];
					board[i][pos-1]=0;
					if(!stack.isEmpty() && tmp==stack.peek()){
						answer+=2;
						stack.pop();
					}
					else stack.push(tmp);
					break;
				}
			}
		}
		return answer;
	}
	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n=kb.nextInt();
		int[][] board=new int[n][n];
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				board[i][j]=kb.nextInt();
			}
		}
		int m=kb.nextInt();
		int[] moves=new int[m];
		for(int i=0; i<m; i++) moves[i]=kb.nextInt();
		System.out.println(T.solution(board, moves));
	}

💬 짚어가기

해당 문제는 stack을 이용하여 풀 수 있다.

나의 풀이에서는 인형의 입력이 상단부터 들어오기 때문에, 들어온 순서대로 인형을 뽑을
수 있도록, Queue<>를 요소로 갖는 List<>로 board를 생성하였다.

moves 배열에 담긴 인덱스를 통해 board의 리스트에 접근한 후 큐에서 하나씩 빼고,
뽑은 인형을 stack에 보관하되, 가장 마지막에 보관된 인형과 같은지 확인하는 방식이다.

강의에서는 2차원 배열로 borad를 생성하고, 인형을 뽑을 시 반복문을 통해 가장 상단의
배열부터 moves 에 담긴 인덱스 요소가 0이 아닐 때 까지 순회하도록 구성하였다.
이후 뽑은 인형에 대한 로직은 동일하다.