[백준] 2493 - 탑(Java)

문제 파악

풀이

당연히 이중 for문을 사용하면 O(N^2)로 시간초과..🥲

쉽게 가보려던 자의 오답

원소를 순회할 때마다 이전 인덱스까지의 수를 참고해야 한다는 사실은 변함이 없으나,
탐색 범위와 탐색 회수를 줄이는 방법을 생각해야겠다

 

그를 위해서 예시로 주어진 [6,9,5,7,4]에서 마지막 원소인 4에 다다랐을 때,
온전한 이전 배열 [6,9,5,7]에서 4보다 큰 수를 찾기보다
[6,9,5,7] => [9,7]에서 가장 최신 원소인 7의 인덱스를 정답 배열에 기록해 주면 될 것이다.

 

`가장 최신의 원소`, `내림차순`(혹은 오름차순)의 특성을 반영하기 위해 단조 스택을 이용하여 풀이하자

 

구현 순서는 순회하는 원소의 값(input)을 바탕으로

 

1. input 값 기준 내림차순 단조 스택 확립

- input 이상의 수들로 구성된 단조 스택 완성
- 만약 input이 가장 큰 값이라면, 스택은 비어있게 된다

 

2. 스택의 최신 값 조회 및 기록

- 스택이 비어있지 않다면, input보다 큰 값이 stack의 최신값이므로 정답에 기록

 

3. 현재 원소 push

의 과정을 거친다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.stream.Collectors;

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());
        StringTokenizer tok = new StringTokenizer(br.readLine(), " ");
        int[] answer = new int[n];
        Stack<Tower> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            int input = Integer.parseInt(tok.nextToken());
            while (!stack.isEmpty() && stack.peek().height < input) {
                stack.pop();
            }
            if (!stack.isEmpty()) {
                answer[i] = stack.peek().idx;
            }
            stack.push(new Tower(i + 1, input));

        }
        System.out.println(Arrays.stream(answer).mapToObj(String::valueOf).collect(Collectors.joining(" ")));
    }

    private static class Tower {
        int idx;
        int height;

        public Tower(int idx, int height) {
            this.idx = idx;
            this.height = height;
        }
    }
}