매출액의 종류

문제 정보

• 사이트 : Infrean 자바 알고리즘 문제 풀이 강의
• 문제 번호 : 5강 3번
• 문제 분류 : Stack

문제 풀이

내가 짠 코드

• 문제의 입력이 아래와 같이 들어오는데 크레인은 위쪽부터 인형을 꺼내므로 입력을 Queue로 받았다.

5
0 0 0 0 0
0 0 1 0 3
0 2 5 0 1
4 2 4 4 2
3 5 1 3 1
8
1 5 3 5 1 2 1 4

• Queue에는 각 열의 인형들만 위에서 부터 순서대로 들어가게 하였고, 크레인의 Moves 배열에 따라 인형을 꺼내어 바구니의 맨 위의 인형과 비교해 같다면 터트리면서 결과 값을 2 증가하고 같지 않으면 바구니에 인형을 추가하는 방식으로 문제를 풀었다.

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int count = 0;
        Queue<Integer>[] qArr = new Queue[n+1];
        Stack<Integer> s = new Stack<>();
        for (int i = 1; i < n+1; i++) {
            qArr[i] = new LinkedList<>();
        }
        
        for (int i = 0; i < n; i++) {
            String[] input = br.readLine().split(" ");
            for (int j = 1; j < n+1; j++) {
            	/** 입력이 0이 아니면 인형이므로 이를 queue에 저장하여 각 열의 인형만 저장하였다. **/
                if(Integer.parseInt(input[j-1]) != 0)
                    qArr[j].add(Integer.parseInt(input[j-1]));
            }
        }
        int m = Integer.parseInt(br.readLine());
        String[] input = br.readLine().split(" ");
        for (int i = 0; i < m; i++) {
            int crane = Integer.parseInt(input[i]);
            /** 해당 열이 비어있지 않다면 **/
            if(!qArr[crane].isEmpty()){
     			/** 인형을 꺼내고 **/
                int doll = qArr[crane].poll();
                /** 바구니에 해당 인형과 동일한 인형이 가장 위에 있다면 터트리고 결과를 기록**/
                if(!s.isEmpty() && s.peek() == doll) {
                    count += 2;
                    s.pop();              
                } else {
                	/** 같지 않다면 바구니에 인형을 추가한다. **/
                    s.push(doll);
                }
            }
        }

        System.out.println(count);
        br.close();
    }
}

정답 코드

• 강의에선 입력 방식을 2차원 배열을 이용해서 풀었다. 2차원 배열의 크기가 크지 않다면 이 방법이 좀 더 쉬울 것 같다.

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int [][] map = new int[n][n];
        int result = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            String[] input = br.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(input[j]);
            }
        }
        int m = Integer.parseInt(br.readLine());
        String[] input = br.readLine().split(" ");
        for (String s : input) {
            int pos = Integer.parseInt(s);
            for (int i = 0; i < map.length; i++) {
                /** 인형이 있다면 **/
                if(map[i][pos-1] != 0){
                    int temp = map[i][pos-1];
                    map[i][pos-1] = 0;
                    /** 바구니가 비어있는지 확인하고 바구니 맨 위에 인형을 꺼내 가져온 인형과 같은 지 비교 (비었을 땐 EmptyStackException 발생하므로 비어있는지 먼저 확인한다.) **/
                    if(!stack.isEmpty() && stack.peek() == temp){
                        /** 같다면 결과 2증가 및 터트림 **/
                        result += 2;
                        stack.pop();
                    } else {
                        /** 같지 않다면 바구니에 인형 추가 **/
                        stack.push(temp);
                    }
                    /** 인형을 꺼낸 뒤 해당 열에서 또 인형을 꺼내는 것을 막기위해서 break **/
                    break;
                }
            }
        }
        System.out.println(result);
        br.close();
    }
}

문제 출처

• Infrean 자바 알고리즘 문제 풀이

썸네일 출처

Image by storyset on Freepik