[BOJ]1874번 : 스택 수열

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

1874번: 스택 수열

 

분류 : 스택

 

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

public class Main {

    static Myscanner sc = new Myscanner();
    static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

    public static void main(String[] args) throws IOException {

        int N = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }
        int index = 0;
        boolean check = true;
        Stack<Integer> st = new Stack<>();
        int num = 1;
        while (index < arr.length) {
            if (num <= arr[index]) {
                st.push(num++);
                sb.append("+" + "\n");
            } else if (st.peek() == arr[index]) {
                index++;
                st.pop();
                sb.append("-" + "\n");
            } else {
                check = false;
                break;
            }
        }

        if (!check) {
            out.println("NO");
        } else {
            out.println(sb);
        }
        out.close();
    }

}

class Myscanner {
    BufferedReader br;
    StringTokenizer st;

    Myscanner() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }

    String nextLine() {
        String str = "";
        try {
            str += br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return str;
    }
}

문제 이름부터 스택을 써야 할 것 같은 문제이다.

그동안 문제 이해가 되지 않아서 계속 넘겨왔었는데 마음 잡고 풀어보자 하고서 시간 투자를 하였다.

index를 지정해놓고 num을 1부터 array [index] 보다 작거나 같을 때까지만 stack에 push를 하고

같을 경우에는 pop을 해주고 해당 인덱스는 더 이상 필요 없으니 index를 늘려준다.

 

특히, 시간 초과를 2번이나 당했는데 처음에는 q에 stack 처럼 넣고 나중에 출력하는 방식 -> 시간 초과,

두 번째는 String에 이어 붙여서 출력하는 방식 => 시간 초과, String을 이어 붙이는 방식은 O(N^2)이기 때문에

StringBuilder를 활용해야 한다.