[스택] 백준 17298. 오큰수 구하기

https://github.com/SUNGIN99/JavaCodingTest/tree/main/%EB%B0%B1%EC%A4%80/Gold/17298.%E2%80%85%EC%98%A4%ED%81%B0%EC%88%98

---

---

현재 위치보다 큰 수를 어떻게 구할 수 있을까 고민한 문제였다.
최대 크기가 백만번이기 때문에, 이중 포문을 사용한다면 무조건 시간 초과 발생

제일 먼저 스택이 떠오름.

• 스택이 비어있다면, 그냥 삽입
• 비어있지 않다면
  • 스택 top이 현재 index의 값보다 크거나 같다면 그냥 삽입
  • 스택 top이 현재 index의 값보다 작다면,
    • 스택 top이 크거나 같을 때 까지 모두 pop하여 pop된 숫자들의 오큰수를 현재 index의 값으로 설정함.

이쁘게 코드화로 한다면?

Stack<Num> stack = new Stack<>();
int[] NGE = new int[n];
for(int i = 0; i<n; i++){
    while(!stack.isEmpty() && stack.peek().value < nums[i].value){
        Num top = stack.pop();
        NGE[top.index] = nums[i].value;
    }

        stack.push(nums[i]);
    }

while(!stack.isEmpty()){
    Num top = stack.pop();
    NGE[top.index] = -1;
}

• 스택이 비어있지 않고, 스택에 들어있는 탑 값이 현재 인덱스의 값보다 작다면

  • 스택 pop(), 그리고 pop된 숫자의 인덱스에 오큰수로 현재 인덱스의 값을 채워넣음.

• 그리고 나서 현재 수를 스택에 삽입

• 모두 순회한 후에, 아직 스택에 남아 있는 값은 오큰수가 존재하지 않는 수

---

시간 복잡도

전체 숫자의 개수 n과 내부에 스택 순회하는 수 (현재 값보다 이전에 작은 값이 존재할 때)
백만개의 오름차순이라고 가정한다면 : O(2n)
백만개의 내림차순이라고 가정한다면 : 스택에 n번 삽입 O(n) + 스택에서 오큰수가 없는 수 채워넣기 O(n)

최악의 경우의수 : O(n)

인줄 알았는데, 마지막 출력부에서 문제가 발생한듯하다.
for문으로 출력출력출력을 하니까 시간초과가 나고, BufferedWriter를 사용하니 통과하였음..

//시간 초과 난 출력부
        for(int i = 0; i<n; i++){
            System.out.print(NGE[i] + " " );
        }

---

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

public class BackJoonMemo {

    static class Num{
        int value;
        int index;

        Num (int v, int i){
           this.value = v;
           this.index = i;
        }
    }
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        Num[] nums = new Num[n];
        for(int i = 0; i<n;i++){
            nums[i] = new Num(Integer.parseInt(st.nextToken()), i);
        }

        Stack<Num> stack = new Stack<>();
        int[] NGE = new int[n];
        for(int i = 0; i<n; i++){
            while(!stack.isEmpty() && stack.peek().value < nums[i].value){
                Num top = stack.pop();
                NGE[top.index] = nums[i].value;
            }

            stack.push(nums[i]);
        }

        while(!stack.isEmpty()){
            Num top = stack.pop();
            NGE[top.index] = -1;
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        for(int i = 0; i<n; i++){
            bw.write(NGE[i] + " " );
        }
        bw.write("\n");
        bw.flush();

        br.close();
        bw.close();

    }

}

---

결과