[백준][Java] 17298번 : 오큰수

[문제 링크]

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

문제 설명

오큰수(NGE) : 현재 원소 Ai보다 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수, 존재하지 않으면 -1

ex) A = {9, 5, 4, 8}인 경우 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1

 

 

 

문제 풀이

문제에서 수열의 크기 N이 최대 1,000,000(10^6) 이다.

그래서 단순하게 현재 원소를 기준으로 오른쪽에 있는 모든 원소를 다 비교해가며 오큰수를 찾으면 O(n^2)로 시간 초과가 나온다.

 

따라서 Stack 을 사용하면 이 문제를 풀 수 있다.(다른 풀이 참고)

 

스택에는 아직 오큰수를 찾지 못한 원소의 인덱스 를 담는다.

for문으로 수열을 돌면서 현재 수와 stack의 top을 인덱스로 하는 수를 비교한다.

 

현재 수 > stack의 top을 인덱스로 하는 수이면 현재 수가 stack의 top을 인덱스로 하는 수의 오큰수이다.

오큰수를 찾으면 stack의 top을 stack에서 pop

이 과정을 현재 수 > stack의 top을 인덱스로 하는 수 를 만족하지 않을 때까지 반복한다.

 

이후 현재 수의 인덱스를 stack에 push

 

 

예시

예시 1) A = {9, 5, 4, 8}

1) 현재 수 9, stack{}

stack이 비어있기 때문에 stack에 9의 인덱스 0 push

→ result : stack{0} nge={0, 0, 0, 0}

 

2) 현재 수 5, stack{0}

현재수(5) < stack.peek()의 수(9) 이므로 stack에 5의 인덱스 1 push

→  result : stack{0, 1} nge={0, 0, 0, 0}

 

3) 현재 수 4, stack{0, 1}

현재수(4) < stack.peek()의 수(5) 이므로 stack에 4의 인덱스 2 push

→  result : stack{0, 1, 2} nge={0, 0, 0, 0}

 

2-1) 현재 수 8, stack{0, 1, 2}

현재수(8) > stack.peek()의 수(4) 이므로 4의 오큰수=8

nge[2]=8, stack에서 2 pop

→  result : stack{0, 1} nge={0, 0, 8, 0}

 

2-2) 현재 수 8, stack{0, 1}

현재수(8) > stack.peek()의 수(5) 이므로 5의 오큰수=8

nge[1]=8, stack에서 1 pop

→  result : stack{0} nge={0, 8, 8, 0}

 

2-3) 현재 수 8, stack{0}

현재수(8) < stack.peek()의 수(9) 이므로 반복 끝, stack에 8의 인덱스 3 push

→  result : stack{0, 3} nge={0, 8, 8, 0}

 

더 이상 탐색할 원소가 없고, stack에 남아있는 0, 3을 인덱스로 가지는 수 9와 8의 오큰수=-1이 된다. 

따라서 nge={-1, 8, 8, -1}

 

 

 

 

 

예시 2) A = {3, 5, 2, 7}

1) 현재 수 3, stack{}

stack이 비어있기 때문에 stack에 3의 인덱스 0 push

→ result : stack{0} nge={0, 0, 0, 0}

 

2) 현재 수 5, stack{0}

현재수(5) > stack.peek()의 수(3) 이므로 3의 오큰수=5

nge[0]=5, stack에서 0 pop이고 stack이 비어있기 때문에 반복 끝, stack에 5의 인덱스 1 push

→  result : stack{1} nge={5, 0, 0, 0}

 

3) 현재 수 2, stack{1}

현재수(2) < stack.peek()의 수(5) 이므로 stack에 2의 인덱스 2 push

→  result : stack{1, 2} nge={5, 0, 0, 0}

 

4-1) 현재 수 7, stack{1, 2}

현재수(7) > stack의 peek()의 수(2) 이므로 2의 오큰수=7

nge[2]=7, stack에서 2 pop

→  result : stack{1} nge={5, 0, 7, 0}

 

4-2) 현재 수 7, stack{1}

현재수(7) > stack의 peek()의 수(5) 이므로 5의 오큰수=7

nge[1]=7, stack에서 1 pop

→  result : stack{} nge={5, 7, 7, 0}

 

4-3) 현재 수 7, stack{}

stack이 비어있기 때문에 stack에 7의 인덱스 3 push

→  result : stack{3} nge={5, 7, 7, 0}

 

더 이상 탐색할 원소가 없고, stack에 남아있는 3을 인덱스로 가지는 수 7의 오큰수=-1이 된다. 

따라서 nge={5, 7, 7, -1}

 

전체코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());

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

        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            //현재 수(numbers[i])와 스택의 최상단 수(numbers[stack.peek()]) 비교
            //현재 수가 오큰수인 경우
            while (!stack.isEmpty() && numbers[stack.peek()] < numbers[i]) {
                nge[stack.peek()] = numbers[i];	//오큰수 저장
                stack.pop();	//stack에서 빼기
            }
            //stack에 현재 수의 인덱스 넣기
            stack.push(i);
        }

        //스택에 여전히 남아있는 수 -> 오큰수가 없는 경우이므로 -1
        while (!stack.isEmpty()) {
            nge[stack.pop()] = -1;
        }

        StringBuilder sb = new StringBuilder();
        for(int s : nge) {
            sb.append(s + " ");
        }

        System.out.println(sb);
    }
}

 

 

오답 코드

처음에 풀었던 방식(시간초과)

for문으로 수열의 처음부터 끝까지 돌면서 현재 원소의 오른쪽에 있는 수들과 비교해서 현재 원소보다 큰 수가 나오면 break, 큰 수가 없다면 -1(오큰수가 존재하지 않음)

하지만 이렇게 하면 최악의 경우 각 원소의 오큰수를 구할 때마다 오른쪽에 있는 모든 원소와 비교해야해서 시간복잡도가 O(n^2)로 시간초과가 발생한다.

예를 들어 수열 A = {9, 8, 7, 6} 일 경우, NGE={-1, -1, -1, -1}인데 각 원소가 오른쪽에 있는 모든 원소와 비교하게 된다. 

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());

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

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n - 1; i++) {
            int j = i + 1;
            boolean flag = false;   //오른쪽에 더 큰 수가 있는지 없는지 확인하는 플래그
            while(j < n) {
                if(numbers[i] < numbers[j]) {
                    sb.append(numbers[j] + " ");
                    flag = true;
                    break;
                }
                j++;
            }
            if(!flag)   sb.append(-1 + " ");
        }

        sb.append(-1);

        System.out.println(sb);
    }
}

 

[참고]

https://st-lab.tistory.com/196