BOJ 17289. 오큰수

BOJ 17298. 오큰수

풀이

오큰수란 입력된 숫자의 오른쪽에 있는 수들 중 가장 큰 수를 의미한다.  입력이 3 5 2 7 일 때
입력 개수가 4개이므로 0부터 3까지 루프를 돌아준다.

i == 0 일 때 
stack은 비어있으므로 stack.push

i == 1 일때 stack.isNotEmpty && number(5) > stack.peek().element(3)은 true 이므로 
while문을 돌아 answer[0]에 5를 넣는다.

그리고 stack에도 element:5, position 1을 push()

i == 2 일 때  stack.isNotEmpty && number(2) > stack.peek().element(5)은 false 이므로  while문을 돌지 않고 stack에 element:2 , position 2를 push()

i == 3  일 때  stack.isNotEmpty && number(7) > stack.peek().element(2)은 true 이므로 
while문을 돌아 answer[2]에 7을 넣는다.

다시 while문을 돌아 stack.isNotEmpty &&  number(7) > stack.peek().element(5)은 true 이므로  answer[1]에 7을 넣는다.

for 루프를 모두 돌았으므로 
남은 answer에는 -1을 채운다.

import java.io.*;
import java.util.Stack;
import java.util.StringTokenizer;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        int[] answer = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        Stack<NGE> s = new Stack<>();

        for (int i = 0; i < N; i++) {
            int number = Integer.parseInt(st.nextToken());
            while (!s.isEmpty() && number > s.peek().element) {
                answer[s.pop().position] = number;
            }
            s.push(new NGE(number, i));
        }

        for (int r : answer) {
            if (r == 0) r = -1;
            bw.write(r+" ");
        }
        bw.flush();
    }
}

class NGE {
    int element, position;

    public NGE(int element, int position) {
        this.element = element;
        this.position = position;
    }
}

import java.util.*

fun main() {
    val N = readLine()!!.toInt()
    val input = readLine()!!.split(" ").map { it.toInt() }
    val stack = Stack<NGE>()
    val answer = MutableList(N) { -1 }

    repeat(N) { i ->
        val number = input[i]
        while (!stack.isEmpty() && number > stack.peek().element) {
            answer[stack.pop().position] = number
        }
        stack.push(NGE(number, i))
    }

    print(answer.joinToString(" "))
}

data class NGE(
    val element: Int,
    val position: Int,
)

풀이소스

github.com/beomjo/algorithm-study/blob/main/BOJ/java/17298.java github.com/beomjo/algorithm-study/blob/main/BOJ/kotlin/17298.kt