백준 17298[자바] java 오큰수

문제 링크: https://www.acmicpc.net/problem/17298

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)을 공백으로 구분해 출력한다.

---

▶해설

입력이 100만이고, 시간이 1초로 주어졌으므로 일반적인 큰 수를 탐색하는 방법으로 푼다면 시간 초과가 발생합니다. 따라서 Stack이나 Queue를 이용해서 풀어야 합니다. 

 

조건을 살펴보겠습니다.

1. 자신보다 오른쪽에 있는 가장 가까운 큰 수를 출력한다.

2. 없다면 -1을 출력한다. 

 

Stack이나 Queue로 풀기 위해선 해당 숫자 뿐만 아니라 해당 숫자가 위치한 인덱스를 포함해서 저장해야 합니다. 이유는 어떠한 수와 비교했을 때 자신의 인덱스에 해당하는 숫자를 넣어야 하기 때문입니다. 

 

인덱스와 숫자를 저장할 Point 클래스를 정의합니다.

class Point{
    int index;
    int cost;

    public Point(int index, int cost) {
        this.index = index;
        this.cost = cost;
    }
}

 

Point 배열을 만들어서 인덱스와 숫자를 넣어줍니다. 

Point[] map = new Point[n];

 

Stack을 선언하고, Stack이 만약 비어있다면, 현재 까지들의 수는 모두 오 큰 수를 가지는 수들입니다. 하지만 Stack에 남아있다면, 현재까지 오 큰 수를 가지지 못한 수들입니다. 

예를 보겠습니다.

ex) 3 5 2 7일 때

1. 3:  Stack size= 0 -> 3을 바로 넣어줍니다. 

 

2. 5: Stack size =1 -> 3과 비교해서 5가 더크므로 3의 인덱스 자리에 5를 넣어주고 pop 합니다. 그 후 5를 넣어줍니다.

 

3. 2: Stack size= 1-> 5와 비교해서 5가 2보다 큽니다. 따라서 2는 Stack에 넣어줍니다. 

 

4. 7: Stack size=2 -> 2와 비교했을 때 2보다 크고, 다음 수은 5와 비교했을 때도 더 큽니다 따라서 2,5의 인덱스에 7을 넣어줍니다. 

 

그렇게 해서 완성되는 5 7 7 -1 됩니다.

for(Point now: map){
    while(!input.isEmpty() && input.peek().cost<now.cost){
        answer[input.pop().index] = now.cost;
    }
    input.add(now);
}

 

전체 코드

import java.io.*;
import java.lang.reflect.Constructor;
import java.lang.reflect.Method;
import java.time.LocalDateTime;
import java.util.*;
import java.util.function.Function;
import java.util.function.Supplier;
import java.util.stream.Stream;

class Point{
    int index;
    int cost;

    public Point(int index, int cost) {
        this.index = index;
        this.cost = cost;
    }
}

public class Main {


    static int n;

    static int[] answer;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        Stack<Point> input = new Stack<>();


        answer = new int[n];
        Arrays.fill(answer,-1);

        int num=0;

        Point[] map = new Point[n];
        String[] s1 = br.readLine().split(" ");
        for(int i=0; i<n; i++){
            map[i] = new Point(i, Integer.parseInt(s1[i]));
        }

        for(Point now: map){
            while(!input.isEmpty() && input.peek().cost<now.cost){
                answer[input.pop().index] = now.cost;
            }
            input.add(now);
        }
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<n; i++){
            sb.append(answer[i]).append(" ");
        }

        System.out.println(sb.toString());

    }
}