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

문제 설명

• 텍스트로 된 설명만으로는 이해가 어렵습니다. 힌트의 그림을 보고 이해하면 좋지만 이러한 이미지가 주어지지 않았을 때에는 직접 예제를 종이에 그려보시는 걸 추천드립니다.

접근법

• 건물의 최소개수 구하는 건 각 건물들의 크기를 최대한 크게 설정하는 것과 동일합니다.
  • 다음과 같은 스카이라인이 주어졌다면

왼쪽처럼 각각의 건물로 보는 것이 아니라 하나의 건물로 보는 게 최소개수를 구하는 데 유리합니다.

• 높이가 같아야 하나의 건물이 될 수 있습니다.
  
  이런 건물은 하나의 건물로 취급하지 않습니다.

• 다음 그림을 보고 어떤 경우 하나의 빌딩으로 확정지을 수 있는지를 생각해 봅시다.
  

• 더 큰 값이 들어온 경우 빌딩을 확정할 수 없습니다.

  • 4번째 값으로 3이 들어오면 이는 파란색 건물과 하나로 간주할 수 있습니다.
  • 4번째 값으로 4이상이 들어오면 갈색 빌딩과 하나로 간주할 수 있습니다.

• 같은 값이 들어온 경우 빌딩을 확정할 수 없습니다.

  • 4번째 값으로 3이 들어오면 이는 파란색 건물과 하나로 간주할 수 있습니다.

• 더 작은 값이 들어온 경우 파란색 빌딩을 확정할 수 있습니다.

  • 뒤에 어떤 빌딩이 와도 스카이라인이 끊기기 때문에 파란색 빌딩과 하나로 간주할 수 없습니다.

비교를 통해 더 작은 값이 들어오는 경우를 처리하는 과정이 필요합니다. 그리고 이 비교는 기존의 값 중 가장 최근 값과 새롭게 들어오는 값을 비교하기 때문에 Stack을 활용하기 좋습니다.

가장 최근 값 하나로 설명드렸지만 결국 새롭게 값이 들어올 때 새롭게 들어오는 값보다 큰 stack안의 모든 빌딩은 하나의 빌딩으로 확정될 수 있습니다. (새롭게 들어오는 빌딩과 연결될 수 없기 때문에)

나머지는 코드의 주석을 통해 설명드리겠습니다.

정답

import java.util.*;

public class Main {
	public static void main(String[] args) {
    	// 초기값 설정
		Scanner sc = new Scanner(System.in);
		int N = Integer.parseInt(sc.nextLine());
		Stack<axis> stack = new Stack<>();
		int answer = 0;
		axis deleted; 

        
		for (int i = 0; i < N; i++) {
			String[] temp = sc.nextLine().split(" ");
            //이번에 들어오는 값을 ax변수로 지정합니다.
			axis ax = new axis(Integer.parseInt(temp[0]),Integer.parseInt(temp[1])); 
            //stack이 비어있으면 '기존의 값 중 가장 최근 값'을 구할 수 없습니다.
			//'기존의 값 중 가장 최근 값'(peek)와 '새롭게 들어오는 값'(ax)을 비교합니다.     
			while (stack.isEmpty() == false && stack.peek().y > ax.y) {
            	//새롭게 들어오는 값이 작으면 가장 최근 값은 빌딩이 확정됩니다.
				deleted = stack.pop();				
                //기존의 값과 연속적으로 붙어있는 동일한 높이의 빌딩들을 함께 확정시켜(스택에서 제거해) 줍니다.
				if(!stack.isEmpty() && stack.peek().y == deleted.y)continue;
                //y가 0인 값은 빌딩으로 취급하지 않습니다.
				if(deleted.y ==0)continue; 
				answer++;				
			}
			//이번 값을 stack에 넣어줍니다.
			stack.add(ax);


		}
		//끝까지 처리 후 stack에 남아있는 값들도 빌딩을 확정시켜 줍니다.
        //직전까지의 코드에서 마지막에 add가 일어나기 때문에
        //마지막으로 들어오는 값의 경우 빌딩을 검사하는 작업이 진행되지 않습니다.
        //그래서 추가적인 작업을 진행해야 합니다.
		while (!stack.isEmpty()) {
			axis temp = stack.pop();
			if(!stack.isEmpty() && stack.peek().y == temp.y)continue;
			if(temp.y ==0)continue;
			answer++;

			
		}
		System.out.println(answer);
	}
}

//x,y값을 함께 관리하기 위해 객체를 생성했습니다.
class axis{
	int x;
	int y;
	public axis(int x, int y) {
		this.x = x;
		this.y = y;
	}
	@Override
	public String toString() {
		return "axis [x=" + x + ", y=" + y + "]";
	}
	
}