[JAVA][Baekjoon] 17298번 오큰수 ⭐️⭐️⭐️⭐️⭐️

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

---

📌 접근 방식

🌟 주어진 수열에서 각 원소에 대해 오큰수를 찾아야 한다. 오큰수란 해당 원소보다 크고, 그 오른쪽에 있는 가장 왼쪽의 수를 의미한다 없으면 -1을 출력!

• 반복문(시간 복잡도가 O(N²))을 이용해 오큰수를 찾는다면 시간 초과가 발생
• 스택에 새로 들어오는 수가 top에 존재하는 수보다 크면 그 수는 오큰수!

1. 스택을 활용하여 수열을 한 번 훑기
2. 새로운 수가 들어오면 스택의 top에 있는 수보다 크다면 그 수는 새로운 수의 오큰수가 된다.
3. 해당 오큰수를 찾으면 스택에서 pop하고, 새로운 수는 스택에 push한다.
4. 스택이 비게 되면, 오큰수가 없는 원소들은 -1로 처리한다.

---

✅ PASS CODE

import java.util.*;
import java.io.*;

public class Main {
    public static void main (String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int []A = new int[n];
        int []ans = new int [n];

        String[] str = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            A[i] = Integer.parseInt(str[i]);
        }
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        for(int i = 1; i < n; i++) {
            while (!stack.empty() && A[i] > A[stack.peek()]){
                ans[stack.pop()] = A[i];
            }
            stack.push(i);
        }
        while(!stack.empty()){
            ans[stack.pop()] = -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();

    }
}

• System.out / Scanner로 입출력을 진행하였는데 시간초과가 발생했다
  ➡️ BufferedWriter / BufferedReader 사용!!
  ❗️flush 해줘야함

---

반응형

📌 느낀 점 

처음에는 오큰수 문제를 풀 때 그냥 반복문을 통해 하나하나 비교했더니 시간 초과가 발생해서 좀 당황했다..... 😅 그래서 스택을 활용해서 다시 구현해보니까 훨씬 빠르게 해결할 수 있었다!

처음에는 오큰수라는 개념 자체가 잘 이해가 안 돼서 시간을 꽤 많이 잡아먹었다... 그래도 문제를 이해하고 나니까 스택에서 push와 pop을 잘 활용해서 구현하면 금방 풀릴 거 같다는 생각이 들었다!