[코딩테스트] 백준 17298번: 오큰수

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

✔️ 17298번: 오큰수 문제

---

💻 구현 코드

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

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        Stack<Integer> stack = new Stack<Integer>(); // 오큰수 찾는 과정을 담을 스택 생성

        int N = Integer.parseInt(br.readLine()); // 입력받을 수열의 크기
        int[] seq = new int[N]; // 수열의 원소들을 담을 배열 생성

        // 입력받은 원소들을 띄어쓰기로 구분해 하나씩 분할
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        // 배열에 원소들 저장
        for (int i = 0; i < N; i++) {
            seq[i] = Integer.parseInt(st.nextToken());
        }

        // 수열을 차례대로 탐색
        for (int i = 0; i < N; i++) {
            // 스택이 비어있지 않고, 스택의 최상단 값이 현재 인덱스의 값보다 작을 동안(현재 인덱스의 값보다 큰 수가 나오기 전까지)
            // 스택 최상단 값을 pop하면서 배열에서의 그 최상단 값을 현재 인덱스의 값으로 치환
            while (!stack.isEmpty() && seq[stack.peek()] < seq[i]) {
                seq[stack.pop()] = seq[i];
            }

            // while문을 빠져나온 후 현재 원소 값을 스택에 push
            stack.push(i);
        }

        // stack에 남아있는 인덱스의 값들은 더이상 뒤에 큰 수가 없기 때문에, -1값으로 치환
        while (!stack.isEmpty()) {
            seq[stack.pop()] = -1;
        }

        StringBuilder sb = new StringBuilder();	// 출력할 결과물을 저장할 StringBuilder
        for (int i = 0; i < N; i++) {
            sb.append(seq[i]).append(' ');
        }

        System.out.println(sb);
    }
}

---

📌 과정 해석

1.

• 첫번째 원소는 이전 원소가 없기 때문에 index 0을 가리키는 0을 스택에 push한다.
  (스택이 비어있기 때문에 while문을 수행하지 않는다.)

stack	배열의 값
[0]	[9, 5, 4, 8]

2.

• Stack의 최상단 값 : 9
• 현재 인덱스 값 : 5
• 5 < 9 이므로 index1를 스택에 push

stack	배열의 값
[0, 1]	[9, 5, 4, 8]

3.

• Stack의 최상단 값 : 5
• 현재 인덱스 값 : 4
• 4 < 5 이므로 index2를 스택에 push

stack	배열의 값
[0, 1, 2]	[9, 5, 4, 8]

4.

• Stack의 최상단 값 : 4
• 현재 인덱스 값 : 8
• 8 > 4 이므로 8보다 큰 수가 나오기 전까지 pop 하면서
  배열에서의 그 최상단 값을 현재 인덱스 값으로 치환

stack	배열의 값
[0, 1]	[9, 5, 8, 8]
[0]	[9, 8, 8, 8]

5.

• Stack의 최상단 값 : 9
• 현재 인덱스 값 : 8
• 8 < 9 이므로 index3를 스택에 push

stack	배열의 값
[0, 3]	[9, 8, 8, 8]

6.

• 더이상 탐색할 수열이 없다.
• stack에 남아있는 인덱스의 값들은 더이상 뒤에 큰 수가 없기 때문에 -1값으로 치환

stack	배열의 값
[0]	[9, 8, 8, -1]
[]	[-1, 8, 8, -1]

💡 최종 결과

-1 8 8 -1

---

• References
  https://st-lab.tistory.com/196