순간을 기록으로

[JAVA] 크레인 인형뽑기 본문

Problem Solving

[JAVA] 크레인 인형뽑기

luminous13 2022. 1. 7. 12:40

문제 유형: 스택

  • 바구니가 한쪽으로만 데이터를 넣는 스택 모양

 

풀이법

우선 스택 문제니 Stack을 선언한다.

그리고 크레인의 작동 위치 횟수만큼 반복되므로 for-each 문을 사용한다.

크레인의 좌우 위치 값은 2차원 board 배열에서 열에 해당되므로 board [][move-1]로 넣어준다. 인덱스의 이므로 -1을 해줘야 한다.

그리고 크레인이 내려가는 모양은 for문으로 구현한다. i가 증가하면서 만약 인형이 없으면(=원소 값이 0이면) 내려가게 되고, 인형이 있으면 스택 바구니 상단과 비교해 같으면 pop()을하고 값을 2 증가시킨다.

만약 같지 않다면 push()를 이용해 바구니에 넣는다.

그리고 인형을 뺏으니 보드에 인형이 있던 위치에 0을 넣는다. 그리고 크레인은 아래로 안 내려가므로 break문을 사용한다.

스택에 비어있는데 peek()을 할 경우 예외가 터지므로 stack에 기본적으로 관련 없는 값 '0'을 처음에 넣어준다.

 

내 풀이

import java.util.Scanner;
import java.util.Stack;

public class Main {

    public int solution(int N, int[][] board, int M, int[] moves) {
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        int answer = 0;


        // 크레인 움직인 횟수만큼 반복
        for (int move : moves) {

            for (int i=0; i<N; i++) {

                if (board[i][move-1] == 0)
                    continue;
                else {
                    if (board[i][move-1] == stack.peek()) {
                        stack.pop();
                        answer += 2;
                    }
                    else {
                        stack.push(board[i][move-1]);
                    }
                    board[i][move-1] = 0;
                    break;
                }
            }

        }
        return answer;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[][] board = new int[N][N];

        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                board[i][j] = in.nextInt();
            }
        }
        int M = in.nextInt();
        int[] moves = new int[M];
        for (int i=0; i<M; i++) {
            moves[i] = in.nextInt();
        }
        System.out.print(T.solution(N, board, M, moves));
    }
}

 

강사 코드

package 인프런.스택과큐.크레인인형뽑기.방법2;

import java.util.Scanner;
import java.util.Stack;

public class Main {

    public int solution(int N, int[][] board, int M, int[] moves) {
        Stack<Integer> stack = new Stack<>();
        int answer = 0;

        for (int move : moves) {    // 크레인의 이동 횟수만큼 반복

            for (int i=0; i<N; i++) {

                if (board[i][move-1] != 0) {
                    int temp = board[i][move-1];
                    board[i][move-1] = 0;

                    if (!stack.isEmpty() && temp == stack.peek()) {
                        stack.pop();
                        answer += 2;
                    }
                    else {
                        stack.push(temp);
                    }
                    break;
                }
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[][] board = new int[N][N];

        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                board[i][j] = in.nextInt();
            }
        }
        int M = in.nextInt();
        int[] moves = new int[M];
        for (int i=0; i<M; i++) {
            moves[i] = in.nextInt();
        }
        System.out.print(T.solution(N, board, M, moves));
    }
}

 

느낀 점

스택을 사용할 줄 안다고 스택 문제를 쉽게 풀 수 있는 게 아니다. 확실한 건 문제를 풀면서 어느 정도 연습이 필요한 것 같다.

어려웠던 점은 문제 자체는 이해했지만 이것을 코드로 어떻게 구현해야 될까에서 많이 고민했던 거 같다.

예를 들면, 크레인이 좌, 우로 이동하는 건 어떻게 코드로 구현하는 걸까? 크레인이 맨 위에 있는 인형을 집는 건 어떻게 구현하는 걸까? 크레인이 인형이 없으면 아무것도 잡지 않는 건 어떻게 구현하는걸까? 등의 생각이 들었다.

'Problem Solving' 카테고리의 다른 글

[JAVA] 재귀로 구현하는 팩토리얼  (0) 2022.01.07
[JAVA] 삽입정렬(Inserting Sort)  (0) 2022.01.07
[재귀] 이진수출력  (0) 2022.01.05
[정렬] 버블정렬  (0) 2022.01.05
[코딩테스트] 괄호문자제거  (0) 2022.01.05
Comments