[백준] 2493 탑(JAVA)

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

2493번: 탑

코드

import java.io.*;
import java.util.Stack;
import java.util.StringTokenizer;

class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Stack<int []> stack = new Stack<>();
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        for (int i = 1; i <= n; i++) {
            int top = Integer.parseInt(st.nextToken());
            while(!stack.empty()){
                if(stack.peek()[0] > top){
                    sb.append(stack.peek()[1] + " ");
                    break;
                }
                stack.pop();
            }
            if(stack.empty())
                sb.append("0 ");
            stack.push(new int[] {top, i});
        }
        System.out.println(sb.toString());
    }
}

풀이

문제의 해결방법을 생각하는데에 있어서는 크게 어려움은 없었지만 실제로 구현신 시간초과가 나와 풀기 까다로운 문제였다. 처음에 내가 생각한 풀이 방법은 다음과 같다.

temp와 origin이름의 스택을 만들어서 전부 입력받아 origin에 저장하고 현재 레이저를 송신하는 타워보다 작은 타워들은 temp에 따로 저장하고 수신받는 타워를 찾은 경우에는 temp에 있는 타워들을 다시 origin에 넣는 식으로 하였다. 그러나 이는 시간복잡도가 n^2이고 n의 범위가 50만이기때문에 최악의 경우 2500억번을 탐색해야하기 때문에 시가오류가 난 것 같다.

그렇게 시간복잡도를 줄이는 방법을 고민하다 현재까지 가장 높은 타워를 저장해놓을까 라는 생각을 해보았지만 이역시도 최악의 경우 2500억번의 탐색을 거쳐야 했다. 그래서 다른 사람들이 한 코드를 보았고 답을 제출하였다.

풀이 방법은 다음과 같다.

먼저 입력을 받으면 현재 스택을 확인한다. 이때 현재 입력받은 값보다 스택에 작은 값이 존재한다면 전부 pop를 시켜버린다. 그러다 만약 입력받은 값보다 큰 값을 스택에서 발견한다면 큰 값이 존재하는 인덱스를 출력하고 스택을 확인하는 반복문은 종료를 해준다.(원래 반복문의 종료조건은 스택이 빌때 까지이다.) 만약 아무것도 출력을 못해주었다면 이는 현재위치에서 송신한 레이저를 아무도 수신받을수 없다는 의미이기에 0을 출력해준다. 그리고 나서 현재위치를 스택에 넣어준다.