https://programmers.co.kr/learn/courses/30/lessons/64061

소스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public int solution(int[][] board, int[] moves) {
    int[] tops = setTop(board);
    
    Stack<Integer> stack = new Stack<Integer>();
    int answer = 0;
    for (int i = 0; i < moves.length; i++) {
        int move = moves[i] - 1;
        int top = tops[move];
        if (top == 0) {
            continue;
        }
        
        int height = board.length - top;
        int value = board[height][move];
        tops[move] = tops[move] - 1;
        
        if (!stack.isEmpty() && (stack.peek() == value)) {
            stack.pop();
            answer += 2;
        } else {
            stack.push(value);
        }
    }
    
    return answer;
}

private int[] setTop(int[][] board) {
    int height = board.length;
    int width = board[0].length;
    int[] tops = new int[width];
    
    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++) {
            if (tops[j] == 0 && board[i][j] != 0) {
                tops[j] = height - i;
            }
        }
    }
    
    return tops;
}

흐름

  1. 인형이 쌓여있는 상자에서 각 열마다 맨 위에 있는 인형의 위치를 배열에 저장함.

  2. 크레인이 뽑을 위치가 담긴 배열 크기(moves) 만큼 loop 돔.

  3. 배열이 0부터 시작하므로, 뽑을 위치(move) 에서 -1 함.

  4. 뽑을 위치에서 맨 위의 위치를 가져오는데 0이면 그 열에 있는 건 모두 뽑아 먹은 것이므로 아무 행동도 하지 않음.

  5. 총 높이에서 그 열에서 제일 위에 있는 인형의 위치를 뻄.

  6. 상자에서 인형을 꺼냄.(value = board[height][move])

  7. 그 열에 한 개 꺼냈으므로, top의 위치를 한 칸 내림.

  8. stack이 비어 있지 않으면서, stack의 top이 현재 뽑은 인형과 같으면 stack에 저장된 인형을 삭제하고, 삭제된 인형의 갯수를 더 함.

  9. 그렇지 않으면 stack에 인형을 추가.

  10. 끝

결과

번호 속도
테스트 1 통과 (0.94ms, 50.1MB)
테스트 2 통과 (0.94ms, 52.4MB)
테스트 3 통과 (1.04ms, 52.6MB)
테스트 4 통과 (2.28ms, 50.6MB)
테스트 5 통과 (0.98ms, 50.9MB)
테스트 6 통과 (0.97ms, 50.6MB)
테스트 7 통과 (1.11ms, 52.4MB)
테스트 8 통과 (1.25ms, 52.1MB)
테스트 9 통과 (1.37ms, 54.4MB)
테스트 10 통과 (1.38ms, 52.5MB)
테스트 11 통과 (1.81ms, 52.7MB)