[Java] 백준 2493 탑

2493 탑 문제 링크

문제

#1

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

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        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());
        }

        for(int i=N-1; i>=0; i--) {
            answer[i] = whereTop(i, arr[i])+1;
        }

        for(int i=0; i<N; i++) {
            bw.write(answer[i]+" ");
        }
        bw.flush();
        bw.close();
    }

    static int whereTop(int level, int target) {
        for(int i=level-1; i>=0; i--) {
            if(arr[i]>target) return i;
        }
        return -1;
    }
}

• 이렇게 하면 O(N^2)이라서 시간초과가 남

#2

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

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        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());
        }

        int a = 0;
        for(int i=0; i<N; i++) {
            if(arr[i] >= arr[a]) {
                if(a==0) {
                    answer[i] = 0;
                    a = i;
                }
                else {
                    a--;
                    i--;
                }
            } else {
                answer[i] = a+1;
                a = i;
            }
        }

        for(int i=0; i<N; i++) {
            bw.write(answer[i]+" ");
        }
        bw.flush();
        bw.close();
    }
}

• 이렇게 하면 O(N)인데.. 그래도 시간초과가 나네..

#3

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

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));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        int[] answer = new int[N];
        Stack<Integer> stack = new Stack<>();

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

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

        for (int i = 0; i < N; i++) {
            bw.write(answer[i] + " ");
        }
        bw.flush();
        bw.close();
    }
}

• 결국 gpt한테 물어봄,,, 하,,,
• 그냥 냅다 다 탐색하지 말고
  • 왼쪽 수가 오른쪽 수보다 작은 경우에는
  • 왼쪽 수가 수신을 받을 일이 없으니까 스택에서 삭제하여
  • 이후 탐색할 때 해당 수를 탐색하지 않도록 함