[백준][17298번] 오큰수

시간초과 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int size = Integer.parseInt(br.readLine());
        Stack<Integer> st = new Stack<>();
        String[] str = br.readLine().split("\\s");

        for(int i=size-1; i>=0; i--){
            int num = Integer.parseInt(str[i]);
            while(!st.empty()){
                if(num < st.peek()){
                    sb.insert(0,st.peek()+" ");
                    st.push(num);
                    break;
                }else{
                    st.pop();
                }
            }

            if(st.empty()){
                sb.insert(0,-1+" ");
                st.push(num);
            }
        }
        System.out.println(sb);
    }
}

시간초과 해결 코드

package backjoon;

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int size = Integer.parseInt(br.readLine());
        Stack<Integer> answer = new Stack<>();
        Stack<Integer> st = new Stack<>();
        String[] str = br.readLine().split(" ");

        for(int i=size-1; i>=0; i--){
            int num = Integer.parseInt(str[i]);
            while(!st.empty()){
                if(num < st.peek()){
                    answer.push(st.peek());
                    st.push(num);
                    break;
                }else{
                    st.pop();
                }
            }

            if(st.empty()){
                answer.push(-1);
                st.push(num);
            }
        }
        while(!answer.empty()){
            bw.write(answer.pop()+" ");
        }
        bw.flush();
    }
}

다른 풀이

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        int[] a = new int[n];
        int[] ans = new int[n];
        String[] temp = bf.readLine().split(" ");
        for (int i=0; i<n; i++) {
            a[i] = Integer.parseInt(temp[i]);
        }
        Stack<Integer> s = new Stack<>();
        s.push(0);
        for (int i=1; i<n; i++) {
            if (s.isEmpty()) {
                s.push(i);
            }
            while (!s.isEmpty() && a[s.peek()] < a[i]) {
                ans[s.pop()] = a[i];
            }
            s.push(i);
        }
        while (!s.empty()) {
            ans[s.pop()] = -1;
        }
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (int i=0; i<n; i++) {
            bw.write(ans[i] + " ");
        }
        bw.write("\n");
        bw.flush();
    }
}

느낀점

다른사람의 풀이와 내 풀이방식이 달랐지만 복잡도가 같았다.

하지만 내 풀이만 시간초과가 났다.

몇시간동안 그 원인을 분석해본 결과
원인은 ‘StringBuilder’의 insert()를 써서 맨앞에 추가할때 시간복잡도가 O(n2)가 되며 성능 저하 가 발생한 것이였다.
출처: stackoverflow / https://stackoverflow.com/questions/5931261/java-use-stringbuilder-to-insert-at-the-beginning

해결법
(위 코드 참조) stack에 추가한다음 마지막에 BufferedWriter을 이용하여 출력했다.