📌 서론.

📚 오늘의 문제.

📝 문제 1.

링크 : https://www.acmicpc.net/problem/6198

1. 문제 설명

   N개의 건물 높이가 주어졌을 때, 각 건물의 옥상에서 볼 수 있는 다른 건물의 수를 계산하는 문제이다. 건물들은 일렬로 배치되어 있으며, 한 건물에서 다른 건물을 보려면 그 사이에 더 높은 건물이 없어야 한다.

2. 문제 풀이

   [ 높이 비교 및 스택 관리 로직 ]

   1. 각 건물의 높이를 순차적으로 확인한다.

   2. 현재 건물의 높이가 스택의 맨 위 건물보다 높을 때, 스택에서 건물을 꺼낸다.

      → 현재 건물이 스택에 있는 모든 건물들을 가리기 때문이다.

   3. 현재 건물이 볼 수 있는 건물의 수는 스택에 남아 있는 건물의 수와 같다.

   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));
   		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
   		int n = Integer.parseInt(br.readLine());
   
   		Stack<Integer> stack = new Stack<>();
   		long count = 0;
   
   		for (int i = 0; i < n; i++) {
   			int height = Integer.parseInt(br.readLine());
   
   			// 현재 건물이 스택의 맨 위 건물보다 높을 때 스택에서 건물을 꺼냄
   			while (!stack.isEmpty() && stack.peek() <= height) {
   				stack.pop();
   			}
   
   			// 스택에 남아 있는 건물들은 현재 건물의 옥상을 볼 수 있음
   			count += stack.size();
   
   			// 현재 건물을 스택에 추가
   			stack.push(height);
   		}
   
   		bw.write(Long.toString(count));
   		br.close();
   		bw.close();
   	}
   }
   

🔑  키워드

[ 시간 복잡도 ]

건물 높이를 순차적으로 비교하고 스택에서 건물을 넣고 빼는 작업을 하기 때문에 시간 복잡도는 O(N)으로 효율적이다.