[BOJ] 2493: 탑 (JAVA)

문제

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

 

여담

처음에 시간 복잡도가 O(N²)이 되는 방식으로 풀었다. N이 최대 500,000개 주어지기 때문에 무조건 시간 초과가 발생할 것이라는 생각을 했지만, 떠오르는 방법이 이것뿐이라 어쩔 수 없었다..

 

결국 풀이를 참고했는데 스택을 이용해서 이렇게 풀 수 있다는 것을 알게 되었다. 역시 문제를 많이 접해봐야 사고가 확장되는 것 같다.

 

풀이

이 문제는 스택을 사용하면 시간 초과없이 쉽게 풀이할 수 있다. 아래의 과정을 각 탑마다 반복해서 풀이하면 된다. 

1. 스택이 비어있는 경우
   • 0을 기록하고, 현재 탑을 스택에 push하기
2. 스택이 비어있지 않는 경우
   • 스택에 peek한 탑의 높이 > 현재 탑의 높이
     • peek한 탑의 번호를 기록하고, 현재 탑을 스택에 push하기
     • 현재 탑의 탐색을 종료하기
   • 스택에 peek한 탑의 높이 < 현재 탑의 높이
     • peek한 탑을 pop하고 2번으로 돌아가기

 

예시

탑의 높이가 6 9 5 7 4일 때 풀이 과정은 다음과 같다.

 

1번 탑

처음에는 스택이 비어있으므로 0을 기록하고 1번 탑을 스택에 push한다.

 

2번 탑

스택에서 peek한 탑의 높이는 6이고, 현재 탑의 높이는 9이다. 즉, 현재 탑이 더 높기 때문에 peek한 탑을 pop한다. 1번 탑을 pop하면 스택이 비어있기 때문에 0을 기록하고 2번 탑을 스택에 push한다.

 

3번 탑

스택에서 peek한 탑의 높이는 9이고, 현재 탑의 높이는 5이다. 즉, peek한 탑이 더 높기 때문에 peek한 탑의 번호(=2번)를 기록하고 3번 탑을 스택에 push한다.

 

4번 탑

스택해서 peek한 탑의 높이는 5이고, 현재 탑의 높이는 7이다. 즉, 현재 탑의 높이가 더 높기 때문에 peek한 탑을 pop한다. 

 

아직 스택이 비어있지 않으므로 다시 비교를 시작한다. 스택에서 peek한 탑의 높이는 9, 현재 탑의 높이는 7이다. 즉, peek한 탑이 더 높기 때문에 peek한 탑의 번호(=2번)를 기록하고 4번 탑을 스택에 push한다.

 

5번 탑

스택에서 peek한 탑의 높이는 7, 현재 탑의 높이는 4이다. 즉, peek한 탑이 더 높기 때문에 peek한 탑의 번호(=4번)를 기록하고 5번 탑을 스택에 push한다.

 

모든 탑을 검사하면 비교하는 과정을 종료한다.

 

코드

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

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 st = new StringTokenizer(br.readLine());
        int[] heights = new int[n];
        for (int i = 0; i < n; i++) {
            heights[i] = Integer.parseInt(st.nextToken());
        }

        Stack<Top> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (stack.isEmpty()) { // 스택이 비어있다면 push & 0 기록
                stack.push(new Top(heights[i], i + 1));
                sb.append("0 ");
            } else {
                while (true) {
                    if (stack.isEmpty()) {
                        sb.append("0 ");
                        stack.push(new Top(heights[i], i + 1));
                        break;
                    }

                    if (stack.peek().height > heights[i]) { // 'peek 높이 > 현재 높이'인 경우
                        // 기록 & push
                        sb.append(stack.peek().idx).append(" ");
                        stack.push(new Top(heights[i], i + 1));
                        break;
                    } else { // 아니라면 그냥 pop
                        stack.pop();
                    }
                }
            }
        }
        System.out.println(sb.toString());
    }

    static class Top {
        int height, idx;

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

---

참고

https://steady-coding.tistory.com/15