17298 오큰수 JAVA

 

https://www.acmicpc.net/problem/17298

 

바로 문제를 간략하게 해석해보겠다.

 

수열 각 요소들의 오큰수를 구하려 한다.

오큰수란 해당 요소보다 오른쪽에 위치하면서도 가장 가까운 큰 수이다.

단, 자신보다 큰 수가 없는 경우 오큰수는 -1이 된다.

시간 복잡도는 최대 수열의 길이가 100만이므로, O(N)의 코드로 구현 가능함을 알 수 있다.

 

이번 문제의 핵심 포인트는 스택을 이용하여 수를 비교하는 거라고 생각했다.

예를 들어 {2, 2, 2, 1, 1, ,1, 7}과 같은 수열이 존재할 때, 마지막 요소를 제외한 모든 요소들의 오큰수는 7이다.

따라서 어떻게 구현할 것이냐면

 

1. 이번엔 수의 값을 비교해야 하기 때문에 수들을 스택이 아닌 배열에 넣어야 한다.

왜냐하면 스택에 값을 넣어버리는 순간 top만 확인할 수 있기 때문이다.

 

2. 그럼 스택은 배열들의 index 번호를 넣을 것이다. 이때 중요한 건, 현재 top의 인덱스 배열 보다 다음 배열의 요소가 값이 크다면, 이게 오큰수다. 오큰수가 구해졌다면 해당 index는 pop을 해버린다. pop을 해버리지 않으면 당연히 값이 뒤죽박죽이 될 것이다. 또한, 아직 이전 index의 오큰수가 정해지지 않았을 수 있으므로 ({2, 2, 1, 7}과 같은 상황 1의 오큰수는 7로 구했지만 {2, 2}의 오큰수는 구하지 못했다.), 이전 인덱스의 오큰수도 동일한 배열의 요소인지, 반복문으로 비교해본다. 즉 앞에 나온 2개의 요소 A(0), A(1)의 오큰수도 7인지 반복문으로 비교해본다는 것이다.

 

3. 마지막까지 반복했다면 남은 것은 아직 오큰수가 정해지지 않은 수들일 것이다. 간단히 예를 들면 맨 앞의 요소가 수열 중 가장 큰 경우나, 마지막 인덱스의 요소의 오큰수는 항상 -1이므로 스택에서 pop되지 않아 배열의 값이 남아있을 것이다. 남아있는 배열의 값에 모두 -1을 저장하면 된다.

 

import java.io.*;
import java.util.Stack;
import java.util.StringTokenizer;

public class S17298 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int[] numArr = new int[N], result = new int[N];
        Stack<Integer> indexStack = new Stack<>();

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; st.hasMoreTokens(); i++)
            numArr[i] = Integer.parseInt(st.nextToken());

        indexStack.push(0); // 바로 peek()하면 예외 발생
        for(int i = 1; i < numArr.length; i++) {

            while(!indexStack.empty() && numArr[indexStack.peek()] < numArr[i])
                result[indexStack.pop()] = numArr[i];
            indexStack.push(i);
        }

        // stack에 남은 인덱스는 오큰수가 없는 것들이므로 모두 -1이다.
        indexStack.stream().forEach(i -> result[i] = -1);

        for(int i : result)
            bw.write(i + " ");
        bw.flush();
    }
}