자바 코딩테스트 강좌, 스택으로 오름차순 수열 만들기

문제 설명

주어진 정수 N에 대해 1부터 N까지의 숫자를 스택을 이용하여 오름차순으로 나열하는 프로그램을 작성하세요. 당신은 수열을 출력하기 전에 필요한 경우 스택에 숫자를 push하고, 숫자를 출력하기 위해 pop할 수 있습니다. 그러나 주어진 순서대로 수를 출력할 수 없을 때는 ‘NO’를 출력해야 합니다.

입력 형식

  • 첫 번째 줄에 정수 N이 주어집니다. (1 ≤ N ≤ 100,000)
  • 다음 N개의 줄에 각 줄마다 출력해야 할 수가 주어집니다. 이 숫자는 1부터 N 사이의 정수입니다.

출력 형식

  • 주어진 수를 오름차순으로 출력하는 방법이 있는 경우, 각 숫자를 순서대로 출력하십시오.
  • 방법이 없는 경우 ‘NO’를 출력하십시오.

예제 입력

    4
    4
    3
    2
    1

예제 출력

    YES
    PUSH
    PUSH
    PUSH
    PUSH
    POP
    POP
    POP
    POP

해설

문제를 해결하기 위해서는 스택 자료구조를 사용하여 숫자를 적절히 조작해야 합니다. 기본 아이디어는 다음과 같습니다:

  1. 수를 1부터 N까지 순차적으로 스택에 push합니다.
  2. 수열의 각 숫자를 pop하여 출력합니다. 이 때, pop하기 전 스택의 최상단 값이 원하는 출력 값과 같아야 합니다.
  3. 스택의 최상단 값이 일치하지 않을 경우, 어떤 숫자도 출력할 수 없는 상태가 되어 ‘NO’를 출력해야 합니다.

구현 단계

아래는 문제를 해결하기 위한 자바 코드를 제시합니다:

    import java.util.*;

    public class StackSequence {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int N = scanner.nextInt();
            int[] sequence = new int[N];
            for (int i = 0; i < N; i++) {
                sequence[i] = scanner.nextInt();
            }

            Stack stack = new Stack<>();
            StringBuilder output = new StringBuilder();
            int current = 1;
            boolean isPossible = true;

            for (int i = 0; i < N; i++) {
                while (current <= sequence[i]) {
                    stack.push(current++);
                    output.append("PUSH\n");
                }
                if (stack.isEmpty() || stack.peek() != sequence[i]) {
                    isPossible = false;
                    break;
                }
                stack.pop();
                output.append("POP\n");
            }

            if (!isPossible) {
                System.out.println("NO");
            } else {
                System.out.println("YES");
                System.out.print(output);
            }

            scanner.close();
        }
    }

코드 설명

위 자바 코드는 다음과 같은 과정으로 동작합니다:

  1. 입력 받기: N과 이후의 N개의 정수를 배열에 저장합니다.
  2. 스택 초기화: 스택을 초기화합니다.
  3. 1부터 N까지 push: 각 숫자를 스택에 push합니다. 연산 중에는 PUSH라는 문자열을 출력합니다.
  4. pop 연산: 현재 수열의 숫자와 스택의 top이 일치하는지 확인하고, 일치하지 않으면 ‘NO’를 출력합니다.
  5. 결과 출력: 모든 수를 성공적으로 pop했다면 ‘YES’와 함께 PUSH, POP 연산을 출력합니다.

시간 복잡도 분석

이 문제에서 스택을 사용하여 각 숫자를 한 번씩만 push 및 pop하므로, 전체 시간 복잡도는 O(N)입니다. 이는 수열을 통해 입력을 처리하는 데 필요한 시간입니다.

결론

이번 강의에서는 스택 자료구조를 사용하여 주어진 수를 오름차순으로 출력하는 방법에 대해 배웠습니다. 코딩테스트에서 스택은 다양한 문제를 해결하는 데 유용한 도구가 될 수 있습니다. 특히, 메모리 활용과 시간 복잡도를 고려한 효율적인 알고리즘 설계에 기여할 수 있습니다.

이 문제를 통해 스택의 특징을 이해하고, 알고리즘 문제를 해결하는 데 있어 어떻게 활용할 수 있는지를 배웠기 바랍니다. 더 나아가 이와 유사한 문제를 스스로 연습하면서 스택을 잘 활용할 수 있는 방법을 스스로 발견해 보시기 바랍니다.