[스택] 백준 17298

문제

1. 크기가 N인 수열(A) 존재
2. 각 원소 A[i]에 관련된 오큰수 NGE[i] 를 구한다
3. 오큰수가 존재하지 않는 경우는 , "-1"로 저장
( 1 <= N <= 1,000,000 )
(* 오큰수 : 오른쪽에 큰 수 중 가장 왼쪽에 있는 수 )
ex) 
A [ 3,5,2,7 ] => NGE [ 5,7,7,-1 ]
A [ 9,5,4,8 ] => NGE [ -1, 8,8,-1 ]

 

문제 분석

• N의 조건이 1,000,000까지 가능하므로 , 일반적인 반복문으로 풀이를 할 경우 시간초과가 난다
• 스택을 이용하여, 풀이 진행
  • 스택에 새로 들어오는 수가 top에 존재하는 수보다 크면 그 수 는 오큰수가 된다
  • 오큰수 구한 후 수열에서 오큰수가 존재하지 않는 숫자에 -1을 출력
  • ex) A[top] < A[index] 인경우 결과에 저장 ( 다 저장한 후에, 스택에 남아있는 인덱스번호는 -1 값 저장 )

ex) A [ 3,5,2 ,7] // result [ ] // stack [ 0, ] 
1. index = 1 시작 ( 5부터 비교 )
2. A[ stack.peek() ] < A [index] ( 3 < 5)-> result[ stack.pop()] = A[index] ( result[0] = 5 ) 
(* stack에는 초기화 인덱스로 0 값이 이미 들어가 있음 -> 그래서 index 1부터 시작 )
3. 이런식으로 비교후, 스택에 남아있는 index의 경우 -1 저장

 

수도코드

size ( 수열크기 )
arr ( A 배열 생성)
result ( 결과 배열 생성 )
stack ( 스택생성 및 초기화 -> 인덱스 0 미리 추가 )

for ( 수열크기만큼 반복 )
{
    while ( 스택이 비어있지 않고, 스택에 top 부분과 A[인덱스] 비교 ){
           result[스택 pop()] = arr[인덱스] 저장
     }
     
     while(스택이 비어있지 않으면)
     {     result [스택 pop()] = - 1 저장 }
   
     while ( 수열 크기 ) {
            결과 출력 
     }
}

 

구현 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;

public class App {
    public static void main(String[] args) throws Exception {
        
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(buf.readLine());
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(buf.readLine());

        int [] arr = new int[size];
        int [] result = new int[size];

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

        Stack<Integer> stack = new Stack<>();
        stack.push(0);

        

        for(int i = 1; i<size; i++){
            
            while(!stack.isEmpty() && arr[stack.peek()] < arr[i]){
                result[stack.pop()] = arr[i];
            }
            stack.push(i);
        }

        while(!stack.empty()){
            result[stack.pop()] = -1;
        }

        for (int i =0; i< size; i++){
            bw.write(result[i] + " ");
        }

        bw.write("\n");
        bw.flush();
        buf.close();

    }
}