백준 17298번 : 오큰수 자바

 

🧫 문제 분석

 

✔️ 출처

백준 17298번 오큰수 골드 4

 

📖 문제

 

오큰수는 현재 요소보다 크면서 가장 왼쪽에 있는 수이다.

그렇다고 무작정 모두 비교하며 찾기에는 O(n^2)이 걸린다. 수열의 크기가 100만까지인 걸로 보아 1초안에는 절대로 불가능하다.

 

수열을 잘 생각해보자

문제에서 [3, 5, 2, 7] 을 보면

3은 바로 뒤 5가 있으므로 5

5 와 2는 7이 오큰수가 된다. 

 

오른쪽 수가 크지 않다면 담아놓고

담아놓은 수보다 큰 수가 나오면 이 수가 오큰수가 된다.

 

이렇게 사용할 수 있는 자료구조가 스택이다. 

 

사실 단순한 스택문제이다. 

 

 

---

🔅 문제 풀이

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

public class Main {

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

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        int[] answer = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        stack.push(new int[] {arr[0], 0});

        for (int i = 1; i < n; i++) {
            // 현재 수가 오큰수라면 알맞는 위치에 오큰수 저장
            while (!stack.isEmpty() && stack.peek()[0] < arr[i]) {
                int[] num = stack.pop();
                answer[num[1]] = arr[i];
            }
            // 현재 수가 stack안 수들의 오큰수가 아니라면 담아놓기
            stack.push(new int[] {arr[i], i});
        }


		// 오큰수가 없었던 수들은 -1로 처리
        while (!stack.isEmpty()) {
            int[] num = stack.pop();
            answer[num[1]] = -1;
        }

        for (int i : answer) {
            sb.append(i).append(" ");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

 

 

 

❗ 오답노트 / 필요한 지식

1.  배열은 순서를 맞추기위한 최고의 자료구조라고 생각한다.