[BOJ][JAVA] 17298 오큰수

백준 17298 오큰수
문제 링크 : https://www.acmicpc.net/problem/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,000,000개의 수에 대해서 각각 오른쪽에 있는 모든 수를 탐색하는 경우 (완전탐색)
최악의 경우 999,999 + 999,998 + 999,998 ... + 3 + 2 + 1 의 연산이 필요하다 O(N^2)
즉, 1,000,000 * 500,000 = 5000억번의 연산 => 시간초과
연산을 줄일 수 있는 알고리즘 필요

탐색을 하는데 중복된 연산을 줄이는 방법을 생각해 보자
답을 찾아야 하는 수를 기준으로 탐색하지 않고
탐색하는 수가 정답이 되는 수를 찾으면 O(N)번만에 할수 있지 않을까?

JAVA에서 입력 클래스 scanner와 출력 메소드 system.out.println은 기본적으로 실행시간이 매우 길다.
따라서 입력은 BufferedReader를 사용하고
출력은 StringBuilder를 이용하여 한번에 출력하거나, BufferedWriter를 이용하여 출력한다는 것은 기본적인 상식!

---

풀이 & 코드

예제 {3,5,2,7}에서 3의 오큰수는 3을 기준으로 오른쪽으로 탐색하며 오큰수를 찾는다.(완전 탐색)
그러나 3을 오큰수로하는 왼쪽의 숫자를 찾고 업데이트 하는 방식을 이용해보자.

3의 경우에는 가장 맨 처음 숫자로서 3을 오큰수로 갖는 숫자는 없다.
5의 경우 5를 오큰수로 갖는 숫자는 3이다.
2의 경우 2를 오큰수로 갖는 숫자는 없다.
7의 경우 7을 오큰수로 갖는 숫자는 5와 2이다.

즉, 오른쪽으로 탐색을 하되, 해당 인덱스의 숫자를 오큰수로 할수 있는 숫자들을 어떤식으로 저장할것인가를 고민해보자.

index에는 오큰수를 찾지 못한 녀석들이 들어가게 된다.

오큰수를 찾지 못한 녀석들을 index에 기록하고 (현재 탐색중인 녀석들)
탐색하면서 탐색하고있는 숫자가 오큰수인 녀석들(index에 있는)을 업데이트 해준다.

최종적으로 오큰수를 찾지 못한녀석들을 -1로 업데이트 해준다.

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

public class Main {
    static int N;
    static int[] A;
    static int[] index;

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

        N = Integer.parseInt(br.readLine());
        A = new int[N + 1];
        index = new int[N + 1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        int top = 0;
        index[top] = 0;
        for (int i = 1; i < N; i++) {
            while (true) {
                if (top < 0 || A[index[top]] >= A[i]) break;
                A[index[top--]] = A[i];
            }
            index[++top] = i;
        }

        while (true) {
            if (top < 0) break;
            A[index[top--]] = -1;
        }//스택에 남아있는 친구들 -1로 업데이트

        for (int i = 0; i < N; i++) {
            bw.write(A[i] + " ");
        }
        bw.flush();
        bw.close();
    }
}

연산은 기본적으로 2N으로 시간복잡도 O(N)만에 가능해진다.

놓친점

index[]는 stack을 사용하면 쉽게 구현 가능하다.

후기

요즘 코테에서 고급알고리즘을 사용하는 문제는 지양한다고 하지만 시간복잡도를 줄이는 개념은 필요하므로 이런식의 문제는 조금 괜찮은것 같다.
완전탐색으로 풀수있지만 조금더 효율적으로 풀수있도록 고민해볼 수 있는 좋은 문제다.