https://www.acmicpc.net/problem/1863
[문제]
도시에서 태양이 질 때에 보이는 건물들의 윤곽을 스카이라인이라고 한다. 스카이라인만을 보고서 도시에 세워진 건물이 몇 채인지 알아 낼 수 있을까? 건물은 모두 직사각형 모양으로 밋밋하게 생겼다고 가정한다.
정확히 건물이 몇 개 있는지 알아내는 것은 대부분의 경우에 불가능하고, 건물이 최소한 몇 채 인지 알아내는 것은 가능해 보인다. 이를 알아내는 프로그램을 작성해 보자.
[입력 조건]
- 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000) 첫 번째 지점의 x좌표는 항상 1이다.
[코드]
import java.util.*;
public class BaekJoon_1863 {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
Stack<Integer> stack=new Stack<>();
int[] height=new int[50002];
int n=sc.nextInt();
for(int i=0;i<n;i++) {
int x=sc.nextInt();
int y=sc.nextInt();
height[i]=y;
}
int result=0;
for(int i=0;i<=n;i++) {
/*
* i 위치에서 고도가 낮아지면 height[i] 보다 큰 높이들 모두 삭제
* 건물 개수 증가
*/
while(!stack.isEmpty()&&stack.peek()>height[i]) {
result++;
stack.pop();
}
// 고도가 같다면 넘어가기
if(!stack.isEmpty()&&stack.peek()==height[i])
continue;
// 값 추가
stack.add(height[i]);
}
System.out.println(result);
}
}
[고찰]
문제를 몇번을 읽어봐도 문제 자체가 이해가 가지 않아 다른 사람의 포스팅을 참고했다. 코드로만은 이해가 잘 가지 않아 문제의 밑 결과 그림에 집중하니 그릴 수 있는 모든 직사각형을 찾는 것과 같은 문제라는 것을 알았다. 무엇을 구해야 하는지 알고 나니 코드가 이해가 갔지만 스스로 푼 문제가 아니기 때문에 다음에 다시 한 번 풀어봐야겠다.
'백준' 카테고리의 다른 글
[백준_7490번] 0 만들기 (0) | 2023.09.26 |
---|---|
[백준_2018번] 수들의 합 5 (0) | 2023.09.24 |
[백준_4485번] 녹색 옷 입은 애가 젤다지? (0) | 2023.09.22 |
[백준_20922번] 겹치는 건 싫어 (0) | 2023.09.22 |
[백준_2668번] 숫자고르기 (0) | 2023.09.19 |