[BOJ] 17298번 : 오큰수 (JAVA/자바)

문제

---

알고리즘 고민

해당 문제는 n번째 숫자를 n+1 번부터 n번째 숫자 보다 큰 숫자중에 가장 왼쪽에 있는 숫자를 출력하는 문제이다.

 

처음에는 투포인터 방식으로 right가 큰숫자를 찾고 left를 진행하고 도달하면 right가 큰숫자를 찾고 left를 다시 진행하고 하는 방식을 생각했다. 하지만, 하나 문제가 있었는데 만약 left를 진행하면서 right 숫자를 써주던 중에 left숫자가 left+1 숫자보다 크다면 right가 갱신될 가능성이 있다는 것이다.

 

예제 입력 중 2번을 통해 확인할 수 있다.

4
9 5 4 8

먼저, 4개의 숫자 9, 5, 4, 8을 입력받게 된다.

이후 left = 0, right = 0 에서 시작하고

left == right 이므로 right를 진행시킨다. 하지만 현재 숫자인 9보다 큰 숫자는 없기에 right는 maxLength 인 4가 되고 -1을 출력하게 된다. 이후 left 를 진행시켜 5가 됬을때 5의 오큰수는 8이다. 하지만 right는 4이기에 -1을 입력하려한다. 

 

이를 방지하기 위해서 left+1이 left보다 작을 때 right를 left+1 부터 다시 찾게 시킨다면 약 30% 정도에서 시간 초과가 나게 된다. 이러한 문제에 의해 이후 Stack 방식을 이용해서 문제를 풀었다.

 

Stack에 입력받은 숫자를 차례로 쌓는다. 그러다가 Stack의 맨위의 숫자, 즉 Last In 이 들어오려는 n번째 숫자보다 작다면 현재 이때 Stack 안에 있는 숫자들의 오큰수는 현재 들어오려는 숫자이다. 모두 pop 하면서 n번째 숫자를 오큰수로써 출력해준다. 이후 n번째 숫자를 Stack 넣고 다시 진행한다.

 

예제 입력 1번

---

JAVA Code

투포인터 (시간초과)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static int findLarge(int[] arr, int right) {
        for (int i = right+1; i < arr.length; i++) {
            if (arr[right] < arr[i]) {
                return i;
            }
        }

        return arr.length;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(br.readLine());

        int[] arr = new int[size];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < size; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        StringBuffer sb = new StringBuffer();
        int left = 0, right = 0;
        while (left < size) {
            if (left == right) {
                right = findLarge(arr, right);
            } else if (left < right) {
                if(right==size) sb.append(-1).append(' ');
                else sb.append(arr[right]).append(' ');
                left++;
                if (left < size && arr[left - 1] > arr[left]) {
                    right = findLarge(arr, left);
                }
            }
        }

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

Stack 방식

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int[] arr = new int[size];
        int[] rightBig = new int[size];
        for (int i = 0; i < size; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < size; i++) {
            if (stack.isEmpty()) {
                stack.push(i);
            } else {
                if (arr[stack.peek()] > arr[i]) {
                    stack.push(i);
                } else {
                    while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
                        int idx = stack.pop();
                        rightBig[idx] = arr[i];
                    }
                    stack.push(i);
                }
            }
        }


        while (!stack.isEmpty()) {
            int idx = stack.pop();
            rightBig[idx] = -1;
        }

        StringBuffer answer = new StringBuffer();
        answer.append(rightBig[0]);
        for (int i = 1; i < rightBig.length;i++) {
            answer.append(' ').append(rightBig[i]);
        }

        System.out.print(answer.toString());
    }
}