백준 17298번 오큰수 문제 스택 활용 풀이 ( Java )

17298번: 오큰수

그 숫자의 오큰수에 해당하는 수를 구하는 것이 아닌

그 숫자가 어떤 수의 오큰수의 해당하는가로 접근하는 아이디어 자체를 생각못해서 헤맸다.

 

그 방법을 알게 되고도 스택에 index대신 값을 저장하는 방식을 택해 또 한참 헤맸다

 

여러모로 어려웠던 문제..

 

나는

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Stack;
 
public 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));
 
        int size = Integer.parseInt(br.readLine());
        // 배열 크기 저장
        String[] numbersStr = br.readLine().split(" ");
        // split 해서 배열에 저장
        int[] numbers = Arrays.stream(numbersStr).mapToInt(Integer::parseInt).toArray();
        // 크기 비교를 위해 int 배열로 변경
        int[] nge = new int[size];
        // 오큰수 담을 배열 생성
        Arrays.fill(nge, -1);
        // 배열 전체를 일단 -1로 초기화
 
        Stack<Integer> stack = new Stack<Integer>();
        // 스택 생성
        
        stack.push(0);
        // 첫번째 인덱스 저장
        
        for (int i = 0; i < size; i++) {
            
            while(!stack.isEmpty()) {
                // 스택이 빌 때 까지 반복한다
                if (numbers[i] > numbers[stack.peek()]) {
                    // stack의 가장 위 숫자와 숫자를 비교해서 크면
                    
                    nge[stack.pop()] = numbers[i];
                    // 그 전에 스택에 있던 숫자를 지우고
                    // 그 숫자를 그 전 인덱스의 오큰수로 넣는다
                } else {
                    // 작거나 같으면
                    stack.add(i);
                    // 스택에 집어 넣고
                    break;
                    // 반복을 종료한다
                }
            }
            
            if (stack.isEmpty()) {
                // 스택이 비어있으면
                stack.add(i);
                // 스택에 인덱스를 집어 넣는다
            }
        }
 
        for (int i = 0; i < size; i++) {
            bw.write(nge[i]+" ");
            // 배열에 있는 값을 출력
        }
        
        bw.flush();
        
        br.close();
        bw.close();
 
    }
 
}

 

이렇게 풀었는데

백준님 풀이는 

 

import java.util.*;
import java.io.*;
 
public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        // 리더 생성
        int n = Integer.parseInt(bf.readLine());
        // 사이즈 입력
        int[] a = new int[n];
        // 배열 생성
        int[] ans = new int[n];
        // 정답 배열 생성
        String[] temp = bf.readLine().split(" ");
        // 임시로 받고
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(temp[i]);
            // int로 변환
        }
        Stack<Integer> s = new Stack<>();
        // 스택 생성
        s.push(0);
        // 첫번째 인덱스 저장
        for (int i = 1; i < n; i++) {
            if (s.isEmpty()) {
                s.push(i);
                // 반복문에 들어올 때 스택이 비어있으면 인덱스 저장 
            }
            while (!s.isEmpty() && a[s.peek()] < a[i]) {
                // 비어있지 않고 숫자가 인덱스 가장 위쪽 숫자보다 크면
                ans[s.pop()] = a[i];
                // 정답 배열 중 스택의 가장 위쪽 숫자와 같은 인덱스에 i번째 숫자를 넣는다 
            }
            s.push(i);
            // 다음번에 비교할 숫자를 stack에 집어넣는다
        }
        
        while (!s.empty()) {
            // 반복문을 다 돌고 나왔는데 스택이 비어있지 않다면 빌 때 까지
            ans[s.pop()] = -1;
            // stack에 쌓인 index에 -1을 넣고
        }
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (int i = 0; i < n; i++) {
            bw.write(ans[i] + " ");
            // 출력한다
        }
        bw.write("\n");
        bw.flush();
    }
}

 

이랬다

 

확실히 짧다. 아오 이 차이 어쩔..