BOJ (Java) 22866번: 탑 보기

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

 

---

풀이

각 건물에서 볼 수 있는 건물들의 번호가 아닌 갯수만 세면 된다는 게 핵심이었다.

스택을 사용하여 현재 건물에서의 왼쪽, 오른쪽으로 보이는 건물의 개수를 각각 센다.

스택은 top에 가장 낮은 높이의 건물이 들어가게 정렬되어 있다.

 

스택 최상단의 건물의 높이(top) < 현재 건물의 높이(now)일 때 now에서 top은 보이지 않으므로, top의 높이가 now보다 클 때까지 스택에서 건물을 빼준다.

이 때 스택에 남아 있는 건물들은 모두 현재 pop된 건물에서 보이므로 pop된 건물에서 보이는 건물의 개수를 스택의 크기만큼 늘려준다. 또한 스택의 top 위치의 건물이 현재 pop된 건물과 가장 가까운 위치이므로 pop된 건물에 저장된 값(nearest)와 비교해 갱신한다.

 

이 때 각 작업의 마지막에 위치한 인덱스(0, N - 1)는 작업에 참여하지 않으므로 한 번 더 반복문으로 탐색해준다.

이 작업은 한 쪽 방향밖에 볼 수 없으므로 양방향으로 진행한다.

---

Java 코드

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

class Main {

    public static void main(String args[]) throws Exception {
    	BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    		
		int N = Integer.parseInt(bf.readLine());
		String[] inputs = bf.readLine().split(" ");
		int[] nums = new int[N];
		Cor[] records = new Cor[N];
		for (int i = 0; i < N; i++) {
			nums[i] = Integer.parseInt(inputs[i]);	
			records[i] = new Cor();
		}
		
		
		Deque<Integer> s = new ArrayDeque<>();
		
		s.push(0);
		for (int i = 1 ; i < N; i++) {
			while (!s.isEmpty() && nums[s.peek()] <= nums[i]) {
				int now = s.pop();
				if (!s.isEmpty()) records[now].cnt += s.size();
				if (!s.isEmpty() && Math.abs(records[now].nearest - now) > Math.abs(now - s.peek())) {
					records[now].nearest = s.peek();
				}
			} 
			s.push(i);
		}
		
		while (!s.isEmpty()) {
			int now = s.pop();
			if (!s.isEmpty()) records[now].cnt += s.size();
			if (!s.isEmpty() && Math.abs(records[now].nearest - now) > Math.abs(now - s.peek())) {
				records[now].nearest = s.peek();
			}
		}
		
		s.clear();
		s.push(N - 1);
		for (int i = N - 2; i >= 0; i--) {
			while (!s.isEmpty() && nums[s.peek()] <= nums[i]) {
				int now = s.pop();
				if (!s.isEmpty()) records[now].cnt += s.size();
				if (!s.isEmpty() && Math.abs(records[now].nearest - now) > Math.abs(now - s.peek())) {
					records[now].nearest = s.peek();
				}
			} 
			s.push(i);
		}
		
		while (!s.isEmpty()) {
			int now = s.pop();
			if (!s.isEmpty()) records[now].cnt += s.size();
			if (!s.isEmpty() && Math.abs(records[now].nearest - now) > Math.abs(now - s.peek())) {
				records[now].nearest = s.peek();
			}
		}
		
		for (int i = 0; i < N; i++) {
			if (records[i].cnt != 0) 
				System.out.println(records[i].cnt + " " + (records[i].nearest + 1));
			else {
				System.out.println("0");
			}
		}
		
    }
    
    static class Cor {
    	int cnt = 0;
    	int nearest = -200_000;
    	
		public Cor() {
			super();
		}
    }
    

 
}