[랜덤 마라톤] 카드 묶음(1771)

1. 문제 풀이 아이디어

• 유효한 카드 묶음을 배열로 저장하고, 이 배열에는 최소값, 최대값, 그리고 인덱스를 포함한다.

• 이 배열을 스택으로 관리하여 문제를 해결할 수 있다.

2. 나의 정답 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder = new StringBuilder();
        int n = Integer.parseInt(bufferedReader.readLine());
        Stack<int[]> stack = new Stack<>();
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for (int i = 0; i < n; i++) {
            int a = Integer.parseInt(stringTokenizer.nextToken());
            int[] cur = {a, a, i};
            if (stack.isEmpty()) {
                stack.add(cur);
                continue;
            }
            while (!stack.isEmpty()) {
                int[] prev = stack.peek();
                if (prev[0] - 1 == cur[1]) {
                    stack.pop();
                    stringBuilder.append(cur[2]).append('\n');
                    cur[1] = prev[1];
                    cur[2] = prev[2];
                } else if (prev[1] + 1 == cur[0]) {
                    stack.pop();
                    stringBuilder.append(cur[2]).append('\n');
                    cur[0] = prev[0];
                    cur[2] = prev[2];
                } else {
                    break;
                }
            }
            stack.push(cur);
        }
        System.out.print(stringBuilder);
        bufferedReader.close();
    }
}

3. 정리

• 입력을 받을 때마다 cur 배열에 묶음의 최소값, 최대값, 인덱스를 저장한다.

• 스택이 비어 있다면 cur를 스택에 추가하고 다음으로 넘어간다.

• 스택이 비지 않은 경우, while문을 통해 스택을 순회한다.

• while문에서 스택의 최상단 배열을 가져와, 다음 조건을 확인한다:
1. 현재 묶음의 최소값이 스택 최상단 배열의 최대값 + 1일 경우:
• 스택에서 최상단 배열을 제거한다.
• 현재 묶음의 인덱스를 stringBuilder에 추가한다.
• 현재 최대값을 이전 배열의 최대값으로 갱신한다.
• 현재 인덱스를 이전 배열의 인덱스로 갱신한다.
2. 현재 묶음의 최대값이 스택 최상단 배열의 최소값 - 1일 경우:
• 위와 동일한 과정을 진행하며, 이번에는 현재 최소값을 이전 배열의 최소값으로 갱신한다.

• 위 조건에 해당하지 않을 경우 while문을 빠져나온다.

• while문을 빠져나온 후, cur를 스택에 추가하고 다음 입력을 처리한다.

• 모든 입력 처리가 완료된 후, stringBuilder에 저장된 결과를 출력하여 문제를 해결한다.