BOJ 14865 - 곡선 자르기 [JAVA]

14865번: 곡선 자르기

  해당 문제는 스택(괄호 문제)을 이용하는 것이다.
  '스택'이라는 아이디어를 떠올리기 전까지 정말 많은 시도를 했을 것이다. 필자도 여러 방법(y축을 기준으로 상승 또는 하강하는 경우, 덮개를 고려하는 경우)을 시도해 보았다. 하지만, 예외 케이스들이 너무 많아서 스택이 아닌 다른 방법을 사용하는 것에는 많은 어려움이 있을 거라고 생각한다.

 

  우선 감을 빨리 잡기 위하여 '곡선 자르기' 문제와 괄호 문제가 어떻게 같은지 그림을 통해서 알아보자.

예시1

  하나의 봉우리에 대해서 왼쪽 부분은 열린 괄호로 오른쪽 부분은 닫힌 괄호이다. (괄호라는 아이디어를 생각하지 못했다고 너무 자책하지 않기를 바란다😅) 또한, 예상한 것처럼 봉우리가 겹쳐져 있는 경우에는 아래와 같이 표현 가능하다.

예시2

예시3

  괄호를 다 만들었다면 문제에서 요구하는 2가지 경우의 개수('다른 봉우리에 의해 포함되지 않는 봉우리'와 '다른 봉우리를 포함하지 않는 봉우리'의 개수)를 쉽게 구할 수 있을 것이다. 하지만 봉우리의 왼쪽 부분(시작점)과 오른쪽 부분(끝점)을 어떻게 괄호로 나타내는지가 이 문제에서 가장 어려운 부분이자 핵심이라고 생각한다. 
  그러므로 문제를 풀 때 고려해야 하는 4가지 요소와 함께 문제를 같이 풀어보자.

 

1. 시작점 찾기 🍔

  문제에서의 주어진 2번 예제 케이스의 꼭짓점('1 1', '1 -1', '-1 -1', '-1 1')을 통해서 항상 왼쪽 밑의 꼭짓점에서부터 시작하는 것이 아니라는 것을 알 수 있다.

  다양한 방법을 이용하여 시작 꼭짓점을 정할 수 있겠지만 가장 왼쪽 밑의 꼭짓점을 시작점으로 하여 문제를 푸는 것이 가장 좋다. (y좌표가 '양수에서 시작하는 경우'와 '음수에서 시작하는 경우'를 나누어 생각해 봤지만 예외 상황이 너무 많다.) 꼭짓점의 개수 N은 4 이상 1,000,000 이하이므로 배열에 저장할 수 있다. 그래서 아래와 같이 배열에 꼭짓점들을 저장하면서 꼭짓점의 위치를 기반으로 시작인덱스(startIdx)를 지정할 수 있다.

xCoordinates  = new int[N]; // 꼭짓점의 x좌표들
yCoordinates = new int[N]; // 꼭짓점의 y좌표들

// 1. 시작점(startIdx)(맨 왼쪽 아래의 지점)을 찾기 위한 활동
int minLeft = Integer.MAX_VALUE;
int minBottom = Integer.MAX_VALUE;
for(int i = 0; i < N; i++) {
    ss = in.readLine().split(" ");
    xCoordinates[i] = Integer.parseInt(ss[0]);
    yCoordinates[i] = Integer.parseInt(ss[1]);

    if(xCoordinates [i] <= minLeft && yCoordinates[i] <= minBottom) {
        minLeft = xCoordinates[i];
        minBottom = yCoordinates[i];
        startIdx = i;
    }
}

 

2. 봉우리의 시작점(열린 괄호)과 끝점(닫힌 괄호) 지정 🍟

  한 개의 봉우리를 만들기 시작하면 해당 봉우리를 무조건 완성해야지 다음 봉우리를 만들 수 있다. (그림을 그려보면 쉽게 그 이유를 알 수 있다.) 이 점에서 착안하여, 봉우리의 시작점 또는 끝점이 될 수 있는 좌표가 나오면 이후에 나오는 봉우리의 끝점 또는 시작점은 무조건 같은 봉우리에 속하게 된다.
  그래서 pointCount라는 변수를 이용하여 pointCount가 2개가 되는 경우(봉우리의 시작점과 끝점이 모두 나온 경우)에 시작점(열린 괄호)과 끝점(닫힌 괄호)으로 이루어진 하나의 봉우리를 만들 수 있다. 시작점(열린 괄호)과 끝점(닫힌 괄호)은 두 지점의 x좌표의 상대적인 위치를 이용하여, x좌표가 작은 경우에는 시작점(열린 괄호)을 부여하고 x좌표가 큰 경우에는 끝점(닫힌 괄호)을 부여한다.

// y로 표시된 현재 꼭짓점의 y좌표와 ny로 표시된 다음 꼭짓점의 y좌표의 부호가 다른 경우에 
// 봉우리의 시작점 또는 꼭짓점이 만들어진다.
if((y > 0 && ny < 0) || (y < 0 && ny > 0)) {
    twoPointsInPeak[pointCount++] = x;
    if(pointCount == 2) { // 봉우리의 시작점과 끝점을 모두 찾은 경우
        // 2개의 부분에서 어느 부분이 시작점(열린 괄호)또는 끝점(닫힌 괄호)인지는 x좌표의 상대적인 위치를 이용하여 표시
        int xCoordinateAtOpenPoint = Math.min(twoPointsInPeak[0], twoPointsInPeak[1]);
        int xCoordinateAtClosePoint = Math.max(twoPointsInPeak[0], twoPointsInPeak[1]);
        points.add(new Point(xCoordinateAtOpenPoint, true));
        points.add(new Point(xCoordinateAtClosePoint, false));
        pointCount = 0;
    }
}

 

3. 봉우리들의 좌표 정렬 🌭

  봉우리들은 x좌표를 기준으로 무작위로 만들 수 있다. 그러므로 모든 봉우리들의 시작점과 끝점을 모두 저장한 후 오름차순으로 정렬해주어야 한다. 이를 위해서 좌표를 나타내는 Point 클래스에 Comparable을 설정해 주고 Collections.sort()를 이용하였다.

// 봉우리의 시작점 또는 끝점을 표시
static class Point implements Comparable<Point> {
    // x좌표
    int x;
    // 봉우리의 시작점인 경우(열린 괄호인 경우) -> true
    // 봉우리의 끝점인 경우(닫힌 괄호인 경우) -> false
    boolean isOpenParenthesis;

    public Point(int x, boolean isOpenParenthesis) {
        super();
        this.x = x;
        this.isOpenParenthesis = isOpenParenthesis;
    }

    @Override
    public int compareTo(Point o) {
        return Integer.compare(x, o.x);
    }
}

// 3. 봉우리를 정렬하는 것 (봉우리는 x좌표를 기준으로 무작위로 생성될 수 있기 때문에 정렬 과정이 필요함)
Collections.sort(points);

 

4. 스택(괄호 문제)을 이용한 요구조건 2가지 카운트 🍕

  이 부분은 매우 간단한다. "다른 봉우리에 의해 포함되지 않는 봉우리"는 stack이 비어있는 상황에서 새로운 봉우리를 만드는 경우에 카운트해 주면 된다. 그리고 "다른 봉우리를 포함하지 않는 봉우리 개수"는 열린 괄호와 닫힌 괄호가 붙어 있는 경우에 카운트해 준다.

// 4. 요구조건 2가지의 개수 카운트
// (1) 다른 봉우리에 의해 포함되지 않는 봉우리 (countA) = 다른 봉우리에 포함되지 않는 새로운 봉우리가 만들어지는 경우 (Stack이 비어있는 상태에서 열린 괄호가 시작되는 경우)
// (2) 다른 봉우리를 포함하지 않는 봉우리 개수 (countB) = 봉우리가 다른 봉우리에 의해 영향을 받지 않는 경우 (열린 괄호 다음에 바로 닫힌 괄호가 따라오는 경우) 
Stack<Character> stack = new Stack<>();
for(int i = 0; i < points.size(); i++) {
    if(points.get(i).isOpenParenthesis) { // 열린 괄호인 경우
        if(stack.isEmpty()) { // (1)의 경우
            countA++;
        }
        stack.push('(');

        if(!points.get(i + 1).isOpenParenthesis) { // (2)의 경우
            countB++;
        }
    }
    else { // 닫힌 괄호인 경우
        stack.pop();
    }
}

 

전체코드 🥞

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

public class Main {

	static StringBuilder sb = new StringBuilder();
	static int N, y, x, ny, nx, countA, countB, pointCount, startIdx, hereIdx, nextIdx;
	static String[] ss;
	static List<Point> points = new ArrayList<>();
	static int[] twoPointsInPeak = new int[2];
	static int[] xCoordinates, yCoordinates;


	// 0. 봉우리의 시작점 또는 끝점을 표시
	static class Point implements Comparable<Point> {
		int x;
		// 봉우리의 시작점인 경우(열린 괄호인 경우) -> true
		// 봉우리의 끝점인 경우(닫힌 괄호인 경우) -> false
		boolean isOpenParenthesis; 

		public Point(int x, boolean isOpenParenthesis) {
			super();
			this.x = x;
			this.isOpenParenthesis = isOpenParenthesis;
		}

		@Override
		public int compareTo(Point o) {
			return Integer.compare(x, o.x);
		}
	}

	public static void main(String[] args) throws Exception {
		
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(in.readLine());
		xCoordinates  = new int[N]; // 꼭짓점의 x좌표들
		yCoordinates = new int[N]; // 꼭짓점의 y좌표들

		// 1. 시작점(startIdx)(맨 왼쪽 아래의 지점)을 찾기 위한 활동
		int minLeft = Integer.MAX_VALUE;
		int minBottom = Integer.MAX_VALUE;
		for(int i = 0; i < N; i++) {
			ss = in.readLine().split(" ");
			xCoordinates[i] = Integer.parseInt(ss[0]);
			yCoordinates[i] = Integer.parseInt(ss[1]);
			
			if(xCoordinates [i] <= minLeft && yCoordinates[i] <= minBottom) {
				minLeft = xCoordinates[i];
				minBottom = yCoordinates[i];
				startIdx = i;
			}
		}

		// 2. 봉우리의 시작점(열린 괄호)과 끝점(닫힌 괄호)을 지정
		hereIdx = startIdx;
		while(true) {
			nextIdx = hereIdx + 1;
			if(nextIdx == N) { 
				nextIdx = 0;
			}
			
			x = xCoordinates [hereIdx];
			y = yCoordinates[hereIdx];
			nx = xCoordinates [nextIdx];
			ny = yCoordinates[nextIdx];
		
			// 봉우리의 시작점 또는 끝점이 만들어지는 상황
			if((y > 0 && ny < 0) || (y < 0 && ny > 0)) {
				twoPointsInPeak[pointCount++] = x;
				if(pointCount == 2) { // 봉우리의 시작점과 끝점을 모두 찾은 경우
					// 2개의 부분에서 어느 부분이 시작점(열린 괄호)또는 끝점(닫힌 괄호)인지는 x좌표의 상대적인 위치를 이용하여 표시
					int xCoordinateAtOpenPoint = Math.min(twoPointsInPeak[0], twoPointsInPeak[1]);
					int xCoordinateAtClosePoint = Math.max(twoPointsInPeak[0], twoPointsInPeak[1]);
					points.add(new Point(xCoordinateAtOpenPoint, true));
					points.add(new Point(xCoordinateAtClosePoint, false));
					pointCount = 0;
				}
			}

			hereIdx++;
			if(hereIdx == N) {
				hereIdx = 0;
			}
			if(hereIdx == startIdx)
				break;
		}
	
		// 3. 봉우리를 정렬하는 것 (봉우리는 x좌표를 기준으로 무작위로 생성될 수 있기 때문에 정렬 과정이 필요함)
		Collections.sort(points);
		
		// 4. 요구조건 2가지의 개수 카운트
		// (1) 다른 봉우리에 의해 포함되지 않는 봉우리 (countA) = 다른 봉우리에 포함되지 않는 새로운 봉우리가 만들어지는 경우 (Stack이 비어있는 상태에서 열린 괄호가 시작되는 경우)
		// (2) 다른 봉우리를 포함하지 않는 봉우리 개수 (countB) = 봉우리가 다른 봉우리에 의해 영향을 받지 않는 경우 (열린 괄호 다음에 바로 닫힌 괄호가 따라오는 경우) 
		Stack<Character> stack = new Stack<>();
		for(int i = 0; i < points.size(); i++) {
			if(points.get(i).isOpenParenthesis) { // 열린 괄호인 경우
				if(stack.isEmpty()) { // (1)의 경우
					countA++;
				}
				stack.push('(');
				
				if(!points.get(i + 1).isOpenParenthesis) { // (2)의 경우
					countB++;
				}
			}
			else { // 닫힌 괄호인 경우
				stack.pop();
			}
		}
		
		System.out.println(countA + " " + countB);
	}
}

 

주의점 (시간복잡도) 🥟

  꼭짓점들을 저장하는 리스트를 ArrayList가 아닌 LinkedList를 사용하지 않도록 주의하자.

List<Point> points = new ArrayList<>(); // O
List<Point> points = new LinkedList<>(); // X

  꼭짓점(N)은 최대 1,000,000개 올 수 있는데 이때 LinkedList를 이용해서 조회하면 시간 초과가 난다. LinkedList의 경우 모든 꼭짓점(1,000,000개)을 조회(O(1,000,000)) 하면 1,000,000,000,000 => 10,000초가 걸리기 때문이다. 이렇게 풀면 N <= 10,000인 서브 테스트만 통과하여 '100점'이 아닌 '부분 점수'만 받게 된다.