[백준] 곡선 자르기

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

14865번: 곡선 자르기

y좌표가 음수이고 가장 왼쪽에 있는 지점을 시작으로 x축을 통과할 때 아래에서 위로 통과하는 경우에는 봉우리가 시작되는 경우이고 위에서 아래로 통과하는 경우에는 봉우리가 끝나는 지점입니다. 모든 봉우리를 담아주고 봉우리가 시작하는 지점과 끝나는 지점을 각각의 status로 나누어서 TreeMap에 저장해둡니다. 그 다음 TreeMap을 탐색하면서 Stack을 통해 봉우리가 시작되는 시점을 담아두고 봉우리가 끝날때 스택에서 빼내면서 스택이 비어있으면 다른 봉우리에 포함되지 않는 봉우리가 되고 체크된 봉우리의 수가 봉우리의 시작과 끝이 같으면 다른 봉우리에 포함되지 않는 봉우리가 되게 됩닏. 

 

import java.util.*;
import java.util.Map.Entry;
import java.io.*;


public class Main_14865 {
	
	static class Point{
		int x, y;
		
		Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	static class Cross implements Comparable<Cross> {
		public int start, end;
		Cross(int start, int end) {
			this.start = start;
			this.end = end;
		}
		
		
		@Override
		public int compareTo(Cross o) {
			return Integer.compare(start, o.start);
		}
	}
	
	static int n;
	static ArrayList<Point> points;
	static ArrayList<Cross> cross;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		n = Integer.parseInt(br.readLine());
		
		points = new ArrayList<>();
		
		Point start = new Point(Integer.MAX_VALUE, Integer.MAX_VALUE);
		int startIndex = -1;
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			
			points.add(new Point(x, y));
			
			// y값이 음수이면서 가장 왼쪽에 있는 좌표를 얻는다.
			
			if (y < 0 && start.x > x) {
				start.x = x;
				start.y = y;
				startIndex = i;
			}
		}
		
		// 봉우리 리스트
		cross = new ArrayList<>();
		
		int x = start.x;
		int y = start.y;
		
		
		Cross save = null;
		TreeMap<Integer, Integer> pointMap = new TreeMap<>();

		// 시작 위치를 기준으로 봉우리를 찾는다.
		for (int i = 1; i < n; i++) {
			Point cur = points.get((startIndex + i) % n);
			
			int ny = cur.y;
			int nx = cur.x;
			
			// 위로 올라올 때는 봉우리를 생성
			if (x == nx && y < 0 && ny > 0) {
				save = new Cross(x, -1);
			}
			
			// 내려갈때는 봉우리를 넣어준다.더 작은 x좌표를 시작점으로 두고 더 큰 x좌표를 끝 지점으로 둔다.
			if (x == nx && y > 0 && ny < 0) {
				save.end = x;
				cross.add(new Cross(Math.min(save.start, save.end), Math.max(save.start, save.end)));
			}
			
			y = ny;
			x = nx;
		}
				
		// 봉우리 시작과 끝에 체크해준다.
		for (int i = 0; i < cross.size(); i++) {
			Cross cur = cross.get(i);
			
			pointMap.put(cur.start, 1);
			pointMap.put(cur.end, -1);
		}
		
		Stack<Integer> stack = new Stack<>();
		int total = 0;
		// 포함되지 않는 봉우리
		int ans1 = 0;
		// 포함하지 않는 봉우리
		int ans2 = 0;
		
		for (Entry<Integer, Integer> entry : pointMap.entrySet()) {
		    int status = entry.getValue();

		    // 봉우리가 시작하는 경우
		    if (status == 1) {
		    	stack.add(total);

		    } else {	// 봉우리가 끝나는 경우
		    	int top = stack.pop();

		    	if (stack.isEmpty()) {
		    		ans1++;
		    	}
		    	
		    	if (top == total) {
		    		ans2++;
		    	}
		    	
		    	total++;
		    	
		    }
		}
		
		System.out.println(ans1 + " " + ans2);
		
	}
}