[백준/JAVA] 17298번: 오큰수

🔺 문제

17298번: 오큰수

 

 

🔺 코드

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[] seq = new int[n]; // 수열 배열
        int[] ans = new int[n]; // 정답 배열
        
        String[] str = br.readLine().split(" ");
        for(int i = 0 ; i < n ; i++) {
           seq[i] = Integer.parseInt(str[i]);
        }
        
        Stack<Integer> stack = new Stack<>();
        stack.push(0);  // 최초 값  push
        
        for(int i = 1 ; i < n ; i++) {
            // 스택이 비어있지 않고, 현재 수열 값이 top
            while(!stack.isEmpty() && seq[stack.peek()] < seq[i]) {
                ans[stack.pop()] = seq[i];    // 정답 배열에 오큰수를 현재 수열로 저장
            }
            stack.push(i);  // 신규 데이터 push
        }
        
        while(!stack.isEmpty()) {
            // 반복문을 다 돌고 나왔는데 스택이 비어있지 않다면, 빌 때까지
            ans[stack.pop()] = -1;  // 스택에 쌓인 idx에 -1을 넣음
        }
        
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i : ans) {
            bw.write(i + " ");
        }
        bw.write("\n");
        bw.flush();
    }
}

✅ 해결 아이디어
✔ 스택
① 스택이 채워져있고, A[idx] > A[top] 인 경우 pop한 인덱스를 이용해 정답 수열에 오큰수 저장.
     pop은 조건을 만족하는 동안 반복.
② 현재 인덱스를 스택에 push하고 다음 인덱스로 넘어가기
③ 1,2를 수열 길이만큼 반복 후, 현재 스택에 남아 있는 인덱스에 -1 저장

 

💥 유의사항

• N의 크기가 큰 관계로(1,000,000) 반복문은 꿈도 꾸지 말어라..

• 스택에 수열의 값이 아닌, 인덱스를 저장!

 

---

🔺 다른 풀이들

- 최고의 설명..

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

 

 

- 과정 설명 굿..

[백준 17298번] 오큰수 (java)

---

💬 느낀 점

이 문제를 보고 스택을 이용할 생각을 하는 거 자체가 큰 미션 아닐까....

복습을 50번은 해야할 것 같다...ㅎ

 

1회독	2회독	3회독	4회독	5회독
V	8/1

 

 

(+ 8/1 2회독)

스택에 수열의 값이 아닌 인덱스 저장하기

---

(참고)

✔ Do it 알고리즘 코딩테스트 자바편