[백준] 17298 오큰수 - 자바

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

17298번: 오큰수

문제 풀이

스택으로 간단하게 풀이할 수 있다. 순차적으로 탐색하며 현재 인덱스를 스택에 보관한다.

보관하기 전에 스택에 있는 인덱스가 가지는 값보다 현재 값이 크다면 그 인덱스의 오큰수는 현재 값이 된다.

그림 예시 몇개만 살펴보면 다음과 같다.

순차탐색이 끝나고도 스택에 남아있는 인덱스 값은 자신보다 큰 수를 찾지 못했으므로 마지막에 -1로 설정해주면 된다.

 

그리고 이를 출력해줄 때 주의해야 한다. 사실 이런 경우는 처음인데 버퍼를 활용해서 출력해주면 더 빠르다는 것쯤은 알고 있었지만 이 차이로 시간초과가 발생해서 무조건 버퍼를 이용한 출력을 사용해야 한다. 반복문을 통해 출력하면 시간초과가 발생한다.

 

코드

package 백준;

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

public class b17298 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        Stack<Integer> s = new Stack<>();

        int n = Integer.parseInt(br.readLine());
        int[] nums = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[] output = new int[n];

        for (int i = 0; i < n; i++) {
            while (!s.isEmpty() && nums[s.peek()] < nums[i]) {
                output[s.pop()] = nums[i];
            }
            s.push(i);
        }

        while (!s.isEmpty()) {
            output[s.pop()] = -1;
        }

        Arrays.stream(output).forEach(x -> sb.append(x+" "));
        System.out.println(sb);
        

//        for (int i = 0; i < n; i++) {
//            System.out.print(output[i] + " ");
//        }

//	     Arrays.stream(output).forEach(x -> System.out.print(x + " "));   

    }
}

느낀점

예전에 프로그래머스에서 똑같은 문제를 풀어봤어서 잘 해결했지만 출력해줄 때 버퍼를 사용하지 않으면 시간초과가 발생하는 건 억까가 아닌가 싶다 ㅎㅎ