문제링크

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

구현방법

처음에 간단하게 하나하나 체크해가면서 진행하면 100만 x100만이라는 엄청난 시간이 걸리는 것을 알게되고 처음 시간 초과를 맞은다음에 STACK을 이용해서 현재 idx와 stack의 가장 위의 값을 비교하면서 진행하여 각 배열에 오큰수를 채워주어서 값을 구했습니다.

처음에 문제이해를 못해서 다른 블로그를 통해서 문제를 이해하는데 도움을 받았습니다.

이해할때 참고한 블로그:

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

구현알고리즘

STACK

CODE

스택을 활용해서 최대한 시간을 줄여서 통과된 코드

package com.backjoon.Gold.p17298;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

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 number[] = new int[N];
        Stack<Integer> stack = new Stack<>();

        StringTokenizer st = new StringTokenizer(br.readLine());
        //값을 먼저 받아둔다.
        for(int idx = 0; idx < N; idx++)
        {
            number[idx] = Integer.parseInt(st.nextToken());
        }

        for(int idx = 0; idx < N ;idx++){
            //비어있는경우 값을 시작하는 idx를 넣어준다.
            if(stack.isEmpty()){
                stack.push(idx);
                continue;
            }

            //만약 stack의 맨위의 값의 idx에 있는 값이 현재 idx보다 작은경우 그값 idx값을 현재 idx값으로 채워주고 다른 들어있는 값들과 비교를 한다.
            while(!stack.isEmpty() && number[stack.peek()] < number[idx]){
                number[stack.pop()] = number[idx];
            }
            //현재의 idx를 push해준다 -> 현재 idx도 찾아봐야하니까
            stack.push(idx);

        }
        //stack에 남아있는 값은 그것보다 큰 오큰수가 존재하지않기때문에 각 idx에 -1을 채워준다.
        while(!stack.isEmpty()){
            number[stack.pop()] = -1;
        }
        StringBuilder sb = new StringBuilder();

        for(int numbers :number){
            sb.append(numbers).append(" ");
        }

        System.out.println(sb);

    }


}

처음 실패한 코드 O(n^2)으로 시간초과

class Solution{
    static class number_idx{
        int number;
        int idx;

        number_idx(int number, int idx){
            this.number=number;
            this.idx = idx;
        }
    }

    public void solution( ) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        Stack<number_idx> stack = new Stack<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int ArrNum[]= new int[N];
        for(int idx = 0; idx <N;idx++){
            ArrNum[idx] = Integer.parseInt(st.nextToken());

        }
        for(int idx = N-1 ;idx >=0;idx--){
            stack.push(new number_idx(ArrNum[idx],idx));
        }
        //출력 저장용
        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()){
            boolean checks = false;
            number_idx numberIdx = stack.pop();
            if(numberIdx.idx == N-1) {
                sb.append(-1);
                continue;
            }
            for(int check = numberIdx.idx+1; check <N;check++){
                if(numberIdx.number < ArrNum[check]){
                    sb.append(ArrNum[check]).append(" ");
                    checks = true;
                    break;
                }
            }
            if(!checks){
                sb.append(-1).append(" ");
            }

        }

        System.out.println(sb);
    }
}