백준_17298_오큰수

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

오른쪽에 나오는 다음 큰수를 찾는 문제

참고 : https://st-lab.tistory.com/196

현재 원소가 이전의 원소보다 작을 때 까지 stack에 수열의 index를 추가
if 현재 원소가 스택의 top 원소를 인덱스로 하는 수열의 원소보다 크게 될 경우 stack의 원소를 pop하면서 해당 인덱스에 해당하는 원소들을 현재 원소로 바꿔주는 것이다.

1. 자기 자신보다 크다
2. 자기 자신보다 오른쪽에 있다
3. 여러 후보군들 중 가장 왼쪽에 있다(가장 먼저 나온 값이다)

현재 원소 보다 큰 인덱스만 스택에 들어감

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

public class Main {
    static int N;
    static int[] arr;
    static int[] ans;

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

        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Stack<Integer> stack = new Stack<>();
      

        for(int i = 0; i < N; i++){
            while(!stack.isEmpty() && arr[stack.peek()] < arr[i]){
                ans[stack.pop()] = arr[i];
            }
            stack.push(i);
        }

        while(!stack.isEmpty()){
            ans[stack.pop()] = -1;
        }

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < ans.length; i++) {
            sb.append(ans[i]).append(" ");
        }

        System.out.print(sb);
    }
}

다시 풀이

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

public class Main {
    static int N;
    static int[] arr;
    static int[] ans;

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

        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Stack<Integer> stack = new Stack<>();
        stack.push(0);

        for(int i = 1; i < N; i++){
            while(!stack.isEmpty() && arr[stack.peek()] < arr[i]){
                ans[stack.pop()] = arr[i];
            }
            stack.push(i);
        }

        while(!stack.isEmpty()){
            ans[stack.pop()] = -1;
        }

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < ans.length; i++) {
            sb.append(ans[i]).append(" ");
        }

        System.out.print(sb);
    }
}

핵심 개념

📌 큰수를 찾는 것이 arr를 오른쪽으로 탐색하는 것!
-> 즉 Stack에는 이전에 탐색한 Index가 임시저장 되는것이다.

유사문제

프로그래머스 - 주식가격

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        int N = prices.length;
        int[] answer = new int[N];
        Stack<Integer> stack = new Stack<>();
        
        for(int i = 0; i < N; i++){
            while(!stack.isEmpty() && prices[stack.peek()] > prices[i]){
                int idx = stack.pop();
                answer[idx] = i - idx;
            }
            stack.push(i);
        }
        
        while(!stack.isEmpty()){
            int idx = stack.pop();
            answer[idx] = N - idx - 1;
        }   
        return answer;
    }
}