[알고리즘]백준 1863: 스카이라인 쉬운거

 

해결방법

스택을 이용하여 문제를 O(N)의 시간 복잡도로 해결할 수 있다.

핵심은 스택에 자신보다 작은 높이만 유지해야 한다.

1. 현재 높이를 스택의 peek() 값과 비교하여, 만약 peek() 값이 현재 높이보다 크다면, 스택에서 해당 값을 pop() 한다. 이때 pop()할 때마다 정답을 증가시킨다.
2. 스택에 값을 넣을 때는 다음 조건을 확인한다.
   • 현재 높이가 0이 아닌 경우
   • 스택의 peek() 값이 현재 높이와 다른 경우

 

코드

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

// 216ms, 스택, O(N)
public class Main_1863_G4_스카이라인쉬운거_스택 {
    public static void main(String[] args) throws IOException{
        // 1. 입력 및 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        int answer = 0;
        Stack<Integer> stack = new Stack();
        
        // 2. Stack
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            // 스택에는 나보다 큰 것들이 들어있으면 안됨
            while(!stack.isEmpty() && (int)stack.peek()>y){
                stack.pop();
                answer++;
            }

            // 높이가 0이면 무조건 건물은 없음
            if(y==0) continue;

            // 동일 높이이면 넣을 필요 없음
            if(!stack.isEmpty() && stack.peek()==y) continue;

            stack.add(y);
        }

        while(!stack.isEmpty()){
            stack.pop();
            answer++;
        }

        // 3. 출력
        System.out.println(answer);
    }
}

 

링크

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