백준 1863번 : 스카이라인 쉬운거

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

1863번: 스카이라인 쉬운거

 

 

 

 

 

 

문제

• 스카이라인을 보고 건물이 최소 몇 채인지 알아내기
• 고도가 바뀌는 지점의 좌표 x와 y가 n개 주어진다
• (1 ≤ n ≤ 50,000)
• (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000)

 

 

입출력 예제

10
1 1
2 2
5 1
6 3
8 1
11 0
15 2
17 3
20 2
22 1

 

결과 : 6

 

 

 

 

 

풀이

• 새로 들어오는 값과 이전의 값들을 비교해야 하므로 스택을 사용해서 푼다
  • 새로 들어오는 고도가 이전의 고도보다 낮으면 → 계속 pop, 결과값 증가
  • 이미 있는 고도면 새로 넣을 필요 X
  • 작업 종료 후, 스택에 남은거만큼 카운트

 

 

 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class BOJ1863 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine()); //고도가 바뀌는 지점의 좌표 개수
		
		Stack<Integer> stack = new Stack<>(); //stack에 y 좌표를 쌓아나감
		
		int answer = 0; //빌딩 개수
		for(int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			
			//고도가 바뀌는 지점의 좌표
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			
			//새로 들어오는 고도가 이전의 고도보다 낮으면, 제거 및 카운트
			while(!stack.empty() && y < stack.peek()) { //연속으로 제거
				stack.pop();
				answer++;
			}
			
			if(!stack.contains(y)) { //없는 고도면 스택에 넣기
				stack.add(y);
			}
		}
		
		
		//종료 후 스택에 남은거 0이상이면 카운트
		for(int i : stack) { 
			if(i > 0) answer++;
		}
		
		//출력
		System.out.println(answer);
	}

}

 

 

 

 

 

결과

 

 

 

 

 

배운점

• 괜히 복잡하게 풀다가 7%대에서 틀렸었다. 스택은 간결하게 풀어야 한다.