17298.오큰수

문제

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

출력

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	512 MB	72922	25497	18035	33.558%
https://www.acmicpc.net/problem/17298

풀이

코드

첫번째 시도

public class 오큰수 {  

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

        //Ai 보다 오른쪽에 있으면서 Ai보다 큰수 중에서 가장 왼쪽에 있는수. 수가없으면 -1 이다.  

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringBuilder sb = new StringBuilder();  
        int N = Integer.parseInt(br.readLine());  

        Stack<Integer> stack = new Stack<>();  

        String[] arr = br.readLine().split(" ");  

        int now = 0;  
        int last = 0;  

        for(int i=0; i<N; i++){  
            now = Integer.parseInt(arr[i]);  

            for(int j=i+1; j<N; j++){  
                if(now < Integer.parseInt(arr[j])) stack.push(Integer.parseInt(arr[j]));  
            }  

            if(stack.isEmpty()){  
                sb.append(-1).append(" ");  
            }else {  
                    last = stack.firstElement();  
                    stack.clear();  
                sb.append(last).append(" ");  
            }  
        }  
        System.out.println(sb);  
        br.close();  
    }  
}

이중 for문을 사용하여 문제가 발생한다.
![[Pasted image 20231012143842.png]]

두번째 시도 - 성공

package 기초1.Day03.정해영;  

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.Stack;  
import java.util.StringTokenizer;  

public class 오큰수 {  

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        Stack<Integer> stack = new Stack<>();  

        int N = Integer.parseInt(br.readLine());  
        int[] seq = new int[N];  

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");  

        for (int i=0; i<N; i++){  
            seq[i] = Integer.parseInt(st.nextToken());  
        }  

        for(int i=0; i<N; i++){  

            //스택이 비어있지 않으면서, 현재의 원소(seq[i])가 스택의 맨위 원소보다 큰경우,  
            //해당조건을 만족할때까지 stack의 원소를 pop 하면서 해당인덱스의 값을 현재의 원소로 바꿔준다.  
            while (!stack.isEmpty() && seq[stack.peek()] <seq[i]){  
                seq[stack.pop()] = seq[i];  
            }  
            stack.push(i); //인덱스를 넣어준다.  
        }  

        /*  
        스택의 모든원소를 pop 하면서 해당 인덱스의 value를 -1로 초기화한다.  
         */        while (!stack.isEmpty()){  
            seq[stack.pop()] = -1;  
        }  

        StringBuilder sb = new StringBuilder();  
        for(int i=0; i<N; i++){  
            sb.append(seq[i]).append(' ');  
        }  

        System.out.println(sb);  
    }  
}