백준 17298 오큰수 자바[java]

• 오큰수

17298번: 오큰수

문제간단설명)

자신보다 오른쪽에 있고, 더 큰 수들중에서 가장 왼쪽에 있는 숫자 출력

 

 

입력받는 수열의 크기가 1~1,000,000 이므로

이중 반복문을 이용하는 방식은 시간초과에 걸린다.

1,000,000 X 1,000,000 = 1조(시간초과)

아래는 시간초과 난 코드이다.

cs

 

이 문제에 스택을 어떻게 적용해야할 지 감이 안 잡혀서 구글링ㅡ.

 

풀이)

입력받은 수열의 인덱스들을 스택에 넣고 빼고 하는 것을 이용한다.

 

스택에 수열의 인덱스를 넣는다.

수열의 다음 값과, 인덱스가 가리키는 수열 값을 비교한다.

 

다음 값이 크다면

아까 값을 다음 값으로 바꿔준다.

 

다음 값에 해당하는 인덱스를 스택에 넣어준다.

이를 반복하고,

스택에 남아 있는 값들이 가리키는 수열들을 "-1" 로 초기화 한다.

왜냐면 스택에 남아 있는 값들은 자신이 가장 큰 값임을 의미하기 때문이다.

 

이것만 보면 이해가 되지 않는다.

예를들어보자.

그림으로 설명)

3 5 2 7수열이 있다.

    

 

                                                                  

여기까지 for문안에 내용이었다.

반복문을 빠져나오면

스택에 남아있는 값들 이용해서 마저 처리해준다.

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException{
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Stack<Integer> stk = new Stack<>();
 
        int N = sc.nextInt();
        int seq[] = new int[N];
 
        for(int i = 0; i < N; i++){
            seq[i] = sc.nextInt();
        }
 
        for(int i = 0; i < seq.length; i++){
 
            while(!stk.isEmpty() && seq[i] > seq[stk.peek()]){
                seq[stk.pop()] = seq[i];
            }
 
            stk.push(i);
        }
 
        while(!stk.isEmpty()){
            seq[stk.pop()] = -1;
        }
 
        for(int i = 0; i < seq.length; i++){
            bw.write(seq[i] + " ");
        }
        bw.flush();
        bw.close();
    }
}