[백준 JAVA] 1874 스택 수열

1874 스택 수열

https://www.acmicpc.net/problem/1874

문제설명

1. N개의 정수가 주어지며, 이 정수들은 1부터 N까지의 자연수이다.
2. 스택을 이용해 주어진 수열을 만들 수 있도록 '+' (push) 및 '-' (pop) 연산을 수행한다.
3. 만약 수열을 만들 수 없다면 "NO"를 출력한다.

접근방식

O(N) 시간복잡도

• Stack은 상수 시간복잡도가 소요되고
• 각 수에 대해 최대 한 번씩 스택에 값을 push하거나 pop할 수 있으므로, N개의 수를 처리하는데 O(N)의 시간이 걸린다.

문제 조건 분석 과정

 

• 스택 초기화: 스택을 생성하고, 입력 수열을 처리할 변수들을 초기화한다.
• 입력 읽기: 주어진 수열의 각 값을 읽어온다.
• 스택 조작:
  • 만약 현재 값이 start (가장 최근에 스택에 넣은 값)보다 크면, 그 사이의 모든 수를 스택에 넣고 '+' 연산을 기록한다.
  • 현재 값이 스택의 최상위 값과 일치하지 않으면 수열을 만들 수 없으므로 "NO"를 출력한다.
  • 그렇지 않으면, 스택에서 값을 제거하고 '-' 연산을 기록한다.
• 결과 출력: 모든 연산이 성공적으로 수행되었다면, 기록된 연산을 출력한다.

 

전체코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        Stack<Integer> stack = new Stack<>();

        int N = Integer.parseInt(br.readLine());
        int start = 0;

        for (int i = 0; i < N; i++) {
            int value = Integer.parseInt(br.readLine());

            if (value > start) {
                for (int j = start + 1; j <= value; j++) {
                    stack.push(j);
                    sb.append('+').append('\n');
                }
                start = value;
            }

            if (stack.isEmpty() || stack.peek() != value) {
                System.out.println("NO");
                return;
            }
            stack.pop();
            sb.append('-').append('\n');
        }

        System.out.println(sb);
    }
}