[백준] 2493. 탑 (Java)

 

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

2493번: 탑

 

💡 스택 자료구조를 이용해 풀기 !

• N은 1 이상 500,000 이하
• 시간 제한 : 1.5초

🔹 틀린 이유 :

• N의 범위와 시간 제한 조건을 제대로 확인하지 못해서 시간초과 문제풀이를 하게 됐다.
• 문제 풀이 방법이 바로 생각 났다고 섣불리 코드부터 짜지 말자..!!
• 문제에서 주어진 변수의 범위와 시간 제한을 확인 후 시간복잡도를 계산 후 문제 풀이를 시작하자.
• 내가 푼 로직은 반복문이 중첩되어 있기 때문에 시간복잡도 = N의 제곱이다.
• 따라서 N이 최댓값일 경우 → 500,000의 제곱이 되기 때문에 무조건 시간 초과가 나는 풀이가 된다.

✅ 정답 풀이

package algo;

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

public class Main_bj_2493_탑 {

    static int N;
    static Stack<Top> stack;
    static class Top {
        int idx,h;

        public Top(int idx, int h) {
            this.idx = idx;
            this.h = h;
        }
    }
    static StringBuilder sb;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());
        stack = new Stack<>();

        st = new StringTokenizer(br.readLine());
        for(int i=1;i<=N;i++) {
            int height = Integer.parseInt(st.nextToken());

// 현재 스택이 비어있지 않으면 하나씩 peek 해가면서 현재 높이보다 같거나 큰 값이 있다면
// idx 번호 StringBuilder에 추가
// 그리고 peek()한 값 아예 stack에서 pop()하기
            while(!stack.isEmpty()) {
                Top top = stack.peek();
                if(top.h >= height) {
                    sb.append(top.idx+" ");
                    break;
                }
                stack.pop();
            }

            if(stack.isEmpty()) {
                sb.append(0+" ");
            }

            stack.push(new Top(i, height));

        } // input end

        System.out.println(sb.toString());
    }

}

❌ 틀린 풀이 (시간 초과🤥)

package algo;

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

public class Main_bj_2493_탑 {

    static int N;
    static int[] top;
    static StringBuilder sb;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());
        top = new int[N+1];
        st = new StringTokenizer(br.readLine());
        for(int i=1;i<=N;i++) {
            top[i] = Integer.parseInt(st.nextToken());
        } // input end

        solve();

        System.out.println(sb.toString());
    }

    private static void solve() {

        sb.append(0+" ");

        for(int i=2;i<=N;i++) {
            int temp_height = top[i];

            int idx = i-1;
            boolean flag = false;
            while(idx > 0) {
                if(temp_height<= top[idx]) {
                    sb.append(idx+" ");
                    flag = true;
                    break;
                }
                idx--;
            }
            if(!flag) sb.append(0+" ");
        }

    }

}