[백준 17298] 알고리즘 101일차 : 오큰수

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

17298번: 오큰수

스택 Java

주어진 수열에서 각 원소마다 본인의 오른쪽에서 가장 가까운 본인보다 큰 수를 출력하는 문제

 

접근방법

이 문제의 포인트는 바로 스택에 오큰수가 될 수 있는 후보들을 저장하고 있다고 생각하고

스택에서 위에 있는 수가 아래에 있는 수보다 항상 커야한다는 점을 생각해야한다!

따라서 스택의 top이 본인보다 작다면 pop해줘야 한다. 스택에는 나(top이 될)보다 큰 값들만 들어있어야 한다.

그렇지 않으면 내 오른쪽에 있는 모든 수를 탐색하는 것과 다를게 없다.

 

 

오답노트

접근방법에 적혀있는 내용을 깨닫지 못하고 스택 두개를 사용해서 풀었는데 당연히 시간초과가 났다.

그리고 두 스택을 이용해서 풀때 stack = stack 하다가 stack이 참조 변수라는걸 망각해서,,clear하고 addAll해줬었다.

필요없게 됐지만.

arraylist set이 안돼서 거꾸로 넣고 reverse해줬다.

 

소스코드

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;

public class S17298_1 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        String[] stringArr = br.readLine().split(" ");
        int[] arr = new int[n];
        for(int i = 0 ; i < n ; i++){
            arr[i] = Integer.parseInt(stringArr[i]);
        }

        ArrayList<Integer> result = new ArrayList<>();

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

        for(int i = n-1 ; i >= 0 ; i--){
            result.add(n-1-i,-1);
            while(!stack.empty()){
                if(arr[i] < stack.peek()){
                    result.set(n-1-i,stack.peek());
                    break;
                }else{
                    stack.pop(); //나보다 크지 않다면 후보에서도 탈락(스택에서 빠짐)
                }
            }
            stack.add(arr[i]);
        }

        Collections.reverse(result);
        bw.write(result.toString().substring(1,result.toString().length()-1).replaceAll(",",""));
        br.close();
        bw.close();
    }
}