[백준] 14298-오큰수(Java)

우선 내가 처음으로 푼 골드문제다...! 물론 완벽히 내힘으로 풀진 못했지만 그래도 어찌저찌 풀었다.
단계별로 풀기에서 스택 카테고리에 있던 문제라 좀 더 힌트가 되지 않았나 싶다.

접근 방법

이 문제를 처음 읽었을 때는 왜 스택을 써야하지..? 라는 생각이 들었다. 처음에 생각한 방법은 이중 포문이였다. 하지만 이중포문을 돌게 되면 시간복잡도가O(n^2)이므로 시간초과로 인해 통과할 수 없었다. 그래서 자연스럽게 스택을 써야하는 이유를 알게 되었다.

로직 설명

먼저 여기서는 수열의 각 원소를 가리키는 변수 t가 필요하고, 답을 구하기 위해 잠시 담아두는 temp스택과 진짜 답을 담는 NGE스택이 필요하다.

t(수열)는 뒤에서부터 차례로 검사한다.

• temp가 비어있으면 (=t보다 오른쪽에 큰수가 없다는 뜻) NGE.push(-1);
temp.push(t);

• temp가 비어있지 않으면, temp에서 t값보다 작은것을 모두 pop해서 빼버림. ==> temp에는 t보다 오른쪽에 있으며, 큰값만 존재.
  • 만약 temp에 있는 모든 원소를 빼서 isEmpty()==true이면,
    NGE.push(-1); temp.push(t);
  • 아니라면,
    NGE.push(temp.peek()); ==> t의 오큰수
    temp.push(t);

구현 코드

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

public class No17298_오큰수 {
    public static void main(String[] args) throws IOException, EmptyStackException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int tc = Integer.parseInt(br.readLine());
        
        String[] str = br.readLine().split(" ");
        
        Stack<Integer> temp = new Stack<>();
        Stack<Integer> NGE = new Stack<>();

        int t=0;

        for (int i=tc-1;i>=0;i--) {
            t=Integer.parseInt(str[i]);

            if(temp.isEmpty()) {
                NGE.add(-1);
                temp.push(t);
            }
            
            else {
                while (!temp.isEmpty() && t >= temp.peek())
                    temp.pop();

                if (!temp.isEmpty()) {
                    NGE.add(temp.peek());
                }
                else {
                    NGE.add(-1);
                }
                temp.add(t);
            }

        }

        
        for (int i=0;i<tc;i++)
             sb.append(NGE.pop()+" ");

        System.out.println(sb.toString());
        
    }
}

이렇게 되면 O(N)까지 시간복잡도를 줄일 수 있게 된다.

처음에는 스택을 3개써서 하느라 또 시간초과가 나왔다. 이런 방법을 생각하는게 아직까진 어렵지만, 풀이방법을 익히고 점점 연습하다 보면 괜찮아질거라고 생각한다!