[BOJ] 17298 - 오큰수

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

www.acmicpc.net/problem/17298

17298번: 오큰수

난이도: 실버 4

사용언어: JAVA

 

풀이

이 문제는 스택을 이용하여 해결할 수 있습니다. 자신보다 오른쪽에 있는 수 중에 자신보다 크고 가장 왼쪽에 있는 수를 찾는 문제이기 때문에, 배열의 가장 뒤에서부터 반복문을 돌며 자신보다 크고 가장 왼쪽에 있는 수를 스택에 저장하는 방법을 사용하였습니다. 

 

아래의 예시를 이용해 설명해보도록 하겠습니다.

 

 

우선 스택에 가장 오른쪽의 값인 7을 넣어줍니다. 7은 가장 우측에 있기 때문에 그 결괏값은 항상 -1일 수밖에 없습니다. 그 뒤에, 2와 7을 비교하면, 7이 더 크기 때문에 2도 스택에 넣어주고, 2의 결괏값으로는 7을 저장해줍니다. 그다음 숫자는 5입니다. 5는 스택의 top 값인 2보다는 크죠. 그럼 2를 pop 해주고 7과 자신을 비교합니다. 자신이 더 작기 때문에 7을 결괏값으로 저장해주고, 자기 자신을 스택에 push 해줍니다. 즉, 자신보다 큰 값을 만날 때까지 pop을 해주는 것입니다.

 

이런 식으로 배열의 처음 부분까지 반복하면 됩니다. 그리고 만일 자신이 스택에 있는 어떤 수보다도 크다면, 스택에 있는 모든 수를 pop 해주고, 자신이 스택의 첫 원소로 들어가면 됩니다. 물론 결괏값은 -1이겠죠.

 

그리고 입력에 중복된 값이 포함될 수도 있습니다. 이 경우도 고려를 하여 문제를 풀어야합니다.

 

import java.io.*;
import java.util.Stack;
import java.util.StringTokenizer;
 
class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        Stack<Integer> stack = new Stack<>();
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N]; // 입력 값을 받는 배열
        int[] result = new int[N]; // 결과를 저장하는 배열
        int i;
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s);
        for (i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
 
        result[N - 1] = -1; // 가장 우측의 값의 결괏값은 -1일 수 밖에 없다.
        stack.push(arr[N - 1]); // 가장 우측 값을 우선 스택에 push
        for (i = N - 2; i >= 0; i--) {
            while (stack.size() != 0 && arr[i] >= stack.peek()) { // 스택의 top에 있는 값과 자신을 비교, 자신과 같은 값이 나와도 pop
               stack.pop(); // 자신보다 큰 원소가 나올 때까지 pop
            }
            if (stack.empty()) // 스택이 비게 된다면 (자신이 기존의 스택에서 가장 큰 값이라면)
                result[i] = -1; // 결괏값은 -1
            else
                result[i] = stack.peek(); // 스택에서 자신보다 큰 값을 만나 pop을 멈추었다면 결괏값은 자신보다 큰 그 값
           stack.push(arr[i]); // 자신을 스택에 push
        }
 
        for (i = 0; i < N; i++) {
            bw.write(String.valueOf(result[i]) + " ");
        }
        bw.flush();
    }
}