[백준] 탑 보기 - 자바(Java)

문제 링크

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

문제 설명

일직선으로 다양한 높이의 건물이 총 N개가 존재한다. 각 건물 옥상에서 양 옆에 존재하는 건물의 옆을 몇 개 볼 수 있는지 궁금해졌다.

i번째 건물 기준으로 i - 1, i - 2, ..., 1번째 건물은 왼쪽에, i + 1, i + 2, ..., N번째 건물은 오른쪽에 있다. 각 건물 사이의 거리는 다 동일하다.

현재 있는 건물의 높이가 L이라고 가정하면 높이가 L보다 큰 곳의 건물만 볼 수 있다. 바라보는 방향으로 높이가 L인 건물 뒤에 높이가 L이하인 건물이 있다면 가려져서 보이지 않는다.

각 건물에서 볼 수 있는 건물들이 어떤것이 있는지 구해보자.

입력

첫번째 줄에 건물의 개수 N이 주어진다. 두번째 줄에는 N개의 건물 높이가 공백으로 구분되어 주어진다.

출력

i(1 ≤ i ≤ N)번째 건물에서 볼 수 있는 건물의 개수를 출력한다.

만약 볼 수 있는 건물의 개수가 1개 이상이라면 i번째 건물에서 거리가 가장 가까운 건물의 번호 중 작은 번호로 출력한다.

제한

• 1 ≤ N ≤ 100,000
• 1 ≤ L ≤ 100,000

입출력 예

입력	출력
8 3 7 1 6 3 5 1 7	1 2 0 3 2 2 2 4 4 3 4 4 6 0

문제 풀이

[고려사항]

건물의 개수(N)의 최대가 100,000(10만) 이므로 시간 복잡도를 고려해서 구현해야한다.

모든 건물을 하나씩 전부 비교하면 O(N^2)이 나와서 시간이 초과되기 때문이다.

[알고리즘, 구현방법]

Stack을 이용해서 문제를 풀어야 시간 초과가 발생하지 않는다.

✅ 정답

건물을 왼쪽에서 오른쪽으로 한번, 오른쪽에서 왼쪽으로 한번씩 순회하면서 각 건물에서 보이는 건물 번호를 저장한다.

이때, 스택 자료구조를 이용해서 스택의 최상위(top)에는 항상 가장 높은 건물 높이를 저장한다.

건물의 양방향을 순회할때, 현재 건물이 스택의 최상위에 있는 건물의 높이보다 크거나 같으면 스택 요소를 제거한다.

즉, 현재 건물이 스택의 최상위 높이보다 낮을때까지 스택 요소를 제거하여 스택의 최상위에는 항상 가장 높은 건물의 높이가 유지되게끔 하는 것이다.

*이러한 자료구조는 모노톤 스택의 종류 중 하나인 단조 감조 스택이다. 

[풀이 과정]

1. 왼쪽 → 오른쪽: 왼쪽에서 볼 수 있는 건물 수와 가장 가까운 건물 번호를 확인
   
   • 단조 감조 스택으로 구현: 스택의 요소들이 내림차순으로 정렬(스택의 맨 아래에서 최상위 방향)
   • 스택이 비어있지 않고, 스택에 현재 건물보다 작거나 같은 높이가 있다면 제거 (= 현재 건물이 스택의 최상위 높이보다 낮을때까지 스택 요소 제거
   • 현재 건물에서 보이는 건물의 개수 = 스택 사이즈(stack.size()) 
   • 스택이 비어있지 않다면(=보이는 건물이 1개 이상이라면), 가까운 건물(nearest[i])에 저장 
2. 오른쪽 → 왼쪽: 오른쪽에서 볼 수 있는 건물 수와 가장 가까운 건물 번호를 확인
   • 왼쪽 → 오른쪽과 기본 구현사항은 동일
   • 현재 건물에서 보이는 건물의 개수에 스택 사이즈 누적합
   • 스택이 비어있지 않고 && (현재 건물의 가까운 건물(nearest)이 이미 값이 없거나 || 오른쪽에서 보이는 건물의 거리가 왼쪽에서 보이는 건물의 거리보다 작다면), 가까운 건물 정보 저장(nearest[i])
3. 각 건물별로 보이는 건물 수와 가장 가까운 건물 번호 출력
   • 이때, 건물 수에 따라 분기태워서 System.out.prinln으로 바로 출력하는 것보다 StringBuilder로 문자열을 만들어서 한번에 출력하는게 성능이 훨씬 향상됨
     • 약 1,000ms 차이 발생 확인

 

X 1차 생각

이 문제는 시간이 오래걸린 문제인데, 처음에는 Stack이랑 Queue를 사용해서 오른쪽에 있는 건물은 Queue에 넣고 하나씩 확인, 왼쪽에 있는 건물은 Stack에 넣고 하나씩 확인했다. 이렇게 하면 모든 건물이 양쪽을 모두 확인하는 방식이 되어서 O(N^2)이 나와 시간이 초과된다. 

다른 포스팅을 참고해서 모노톤 스택이라는 자료구조를 알게되어서, 모노톤 스택에 대해 공부한 다음에 이 문제를 풀었다. 모노톤 스택은 블로그에 정리해두었다.

https://coding-vvon.tistory.com/entry/algorithm-stack-1

 

정답 코드

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

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

        int n = Integer.parseInt(st.nextToken());
        // 건물 번호는 1부터 시작하므로, n+1로 사이즈 할당
        int[] heights = new int[n+1];
        int[] visibleCnt = new int[n+1];
        int[] nearest = new int[n+1];
        // 초기화
        st = new StringTokenizer(br.readLine(), " ");
        for (int i=1; i<=n; i++) {
        	heights[i] = Integer.parseInt(st.nextToken());
        	nearest[i] = -1;
        }

        Deque<Integer> stack = new ArrayDeque<>();
        // 왼쪽에서 볼 수 있는 건물 수와 가장 가까운 건물 번호
        for (int i=1; i<=n; i++) {
        	// 현재 건물보다 작거나 같은 건물은 제외 = 스택의 최상위 요소보다 클 때까지 기존 요소를 제거
        	// 최상위 값은 항상 작은 값이 들어감 (단조 감소 스택)
        	while (!stack.isEmpty() && heights[stack.peek()] <= heights[i]) {
        		stack.pop();
        	}
        	visibleCnt[i] = stack.size();
        	
        	if (!stack.isEmpty()) { // 보이는 건물이 1개 이상인 경우
        		nearest[i] = stack.peek();
        	}
        	stack.push(i);
        }
        
        // 오른쪽에서 볼 수 있는 건물 수와 가장 가까운 건물 번호
        stack.clear();
        for (int i=n; i>0; i--) { 
        	while (!stack.isEmpty() && heights[stack.peek()] <= heights[i]) {
        		stack.pop();
        	}
        	visibleCnt[i] += stack.size(); // 보이는 건물 개수 갱신
        	
        	// 보이는 건물이 할당이 되어있거나, 오른쪽에서 보이는 건물이 더 가까운 경우, 가까운 건물 갱신
        	if (!stack.isEmpty() && (nearest[i] == -1 || stack.peek() - i < i - nearest[i])) {
        		nearest[i] = stack.peek();
        	}
        	stack.push(i);
        }

        // 분기태워서 System.out.println 하는것보다 StringBuilder로 하는게 성능이 훨씬 향상됨
        StringBuilder sb = new StringBuilder();
        for (int i=1; i<=n; i++) {
        	sb.append(visibleCnt[i]);
        	if (visibleCnt[i] > 0) sb.append(" ").append(nearest[i]);
        	sb.append("\n");
        }
        
        System.out.println(sb);
	}
}