Java 백준 문제풀이 (46) 오큰수

 

 

어떻게 푸는지 생각해보면 정말 별 거 아닌 문제인데

막상 풀고 있으면 버벅버벅거리게 되는 문제였다..

 

일단 시간 복잡도 문제로 2중 반복문 O(n^2)가 아닌 스택 O(N)을 활용해야한다는 것은 확실했는데.

머리속에서 그려보면 생각처럼 쉽사리 되지 않는다.

일단 직접 시도해보자.

 

크기가 N인 임의 수열 A(1) ~ A(N)에서 각 A(i)에 대한 오큰수 NGE(i)를 구하는 것이 문제의 목표다.

스택을 활용해서 가장 가까면서도 큰 숫자를 찾는 방법이 무엇인가?

 

아주 단순하다. 그냥 push()하기 전에 peek()으로 뚜껑 열어보고 "어? push하려던 게 더 크네?" 이러면 그 친구가 오큰수다.

"앞에 쌓여 있는 숫자들은요??"

-> pop()으로 계속 꺼내주면서 넣으려고 했던 숫자보다 더 크면 전부 오큰수다.

 

그리고 여기서 문제가 있는데. 이걸 활용해서 어떻게 풀여아할지 생각하는 게 문제다.

난 생각 못했고 그래서 결국 찾아봄 ㅎㅎ.. 어제 찾아보고 풀고 오늘 혼자서 한 번 더 풀었다.

 

문제에서 주는 수열은 배열을 만들어서 따로 보관하고, 스택에는 인덱스만 저장해야 한다.

실제 수를 넣으면 여러 문제로 인해 "이것만 해결하면 정답이 나오는데.. 하.."라는 상황을 맞닥뜨리게 될 것이다.

 

여기까지 알았으면 이제 다 할 수 있겠다..

 

for ( ~ ) {

while ( 뚜껑 열었는데 넣으려던 게 더 크네요 ) {

넣으려던 것보다 큰 수가 나오거나 끝날 때까지 pop = pop으로 튀어나온 인덱스는 넣으려던 숫자가 되겠네요

}

stack.push(i)

}

 

여기서 해결하지 않은 문제는 마지막으로 남은 -1을 어떻게 처리할 것인지.

그건 직접 해보자.

정답 보고 쓰면 재미 없으니까요.

 

정답은 아래에.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
 
        // 수열 1 ~ n
        // 오큰수 NGE(i)
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
 
        Stack<Integer> stack = new Stack<>();
        int[] temp = new int[N];
 
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        for (int i=0; i<N; i++) {
            temp[i] = Integer.parseInt(st.nextToken());
        }
 
        stack.add(0);
        int[] answer = new int[N];
 
        for (int i=0; i<N; i++) {
            // 스택에 값을 넣다가, 기존 존재하는 값보다 큰 값이 들어오면 pop
            while(!stack.isEmpty() && temp[stack.peek()] < temp[i]) {
                answer[stack.pop()] = temp[i];
            }
 
            stack.push(i);
        }
 
        while (!stack.isEmpty()) {
            answer[stack.pop()] = -1;
        }
 
        StringBuilder sb = new StringBuilder();
        for (int i=0; i<N; i++) {
            sb.append(answer[i]).append(" ");
        }
 
        System.out.println(sb);
    }
}