[백준, 자바] 17298번 - 오큰수

오큰수

해당 숫자의 오른쪽에 있는 숫자들 중에서 큰 수이며, 동시에 가장 왼쪽에 있는 수를 출력해야 한다.

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

public class Main2 {

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

        int N = Integer.parseInt(br.readLine());
        int[] result = new int[N];

        String[] tmp = br.readLine().split(" ");

        for(int i = 0; i < N; i++) {
            result[i] = Integer.parseInt(tmp[i]);
        }

        for(int i = 0; i < N; i++) {
            //할것을 다 하고? 민다.
            while(!stack.isEmpty() && result[stack.peek()] < result[i]) {
                //스택이 저장한 주솟값에 존재하는 값이 현재 elem보다 작을 경우
                // 스택의 주솟값을 꺼내서 해당 result[스택의 주솟값]에 현재 elem의 값을 넣는다.
                result[stack.pop()] = result[i];

                //비교의 개념이기는 하나 요소를 a,b를 순차적으로 꺼내서 하는 비교가 아니다. 그래서 틀렸다.
            }
            stack.push(i);
        }

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

        //마지막으로 출력
        for(int i = 0; i < N; i++) {
            sb.append(result[i]).append(i == N -1 ? "" : " ");
        }

        System.out.println(sb);
    }
}

결과

오답 -> 시간 초과(이중 for문)

오답 분석

스택에 항상 값만 담는 것이라고 생각했는데 배열 주소, 즉 인덱스를 담을 생각은 전혀 못 했다.

참고

아래 사이트 그림이 이해가 제일 잘 되었다.
https://st-lab.tistory.com/196