[백준 17298] 오큰수 : Stack

🔎 문제

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

 

 

🎁 문제풀이

문제 해결의 핵심은 스택에 인덱스 정보를 쌓고, 스택에서 pop()한 인덱스를 가지고 정답 수열을 오큰수로 채우는 것이다. 

즉, 입력에서 주어진 수열(array)가 있고, 출력할 정답 수열(answerArray) 그리고 문제 풀이를 위한 스택(myStack)이 필요하다. 

 

입력에서 주어진 수열을 차례대로 확인하며, 

만약 스택에 마지막에 쌓이 값(peek)보다 다음 차례로 들어올 입력 수열의 값이 크다면 이 수열의 값은 '오큰수'에 해당하고, 스택에는 입력 수열의 인덱스를 저장하고, 정답 수열은 스택에 저장된 인덱스 정보를 가지고 해당 인덱스에 오큰수를 저장하는 방법으로 푸는 것이다. (answerArray[myStack.pop()] = array[i])

 

위의 내용을 java 코드로 구현하면 아래와 같다. 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;

public class P17298_오큰수구하기 {

    /**
     * 문제 풀이 방법
     * 1. 첫번째 수열은 스택에 무조건 쌓는다.
     * 2. 두번째 수열부터 마지막 수열까지는 반복으로 검사한다.
     * 3. 만약 스택에 마지막으로 저장된 값(stack.peek()) < 다음 수열 => 스택의 인덱스를 꺼내서 해당 인덱스에 다음 수열 값 저장
     * 4. 만약 스택에 마지막으로 저장된 값(stack.peer()) >= 다음 수열 => stack.push()
     * 5. 반복문이 끝까지 돈 후 값이 비어있는 인덱스에 -1 값 넣기
     *
     * 풀이의 핵심
     * pop한 인덱스를 활용하여 정답 수열에 오큰수 저장
     */
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(br.readLine());
        String arrayString = br.readLine();
        int[] array = new int[size]; 
        for(int i = 0 ; i < size ; i++){ //수열 생성
            array[i] = Integer.parseInt(arrayString.split(" ")[i]);
        }
        int[] answer = new int[size];
        Stack<Integer> stack = new Stack<>();
        
        //첫번째 수열은 무조건 스택에 쌓는다. 
        stack.push(0);
        for(int i = 1 ; i < size ; i++){
            while(!stack.isEmpty() && array[stack.peek()] < array[i]){ //스택의 TOP(INDEX)에 대한 수열의 값 < 들어올 수열의 값
                answer[stack.pop()] = array[i]; //정답 수열의 POP한 INDEX에 들어올 수열의 값 저장
            }
            stack.push(i); //인덱스 저장
        }

        while(!stack.empty()){ //스택이 비워질 때까지
            answer[stack.pop()] = -1; //정답 수열에서 비어있는 인덱스에 -1 저장
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i : answer){
            bw.write(i + " ");
        }
        bw.close();
    }
}