Level 2: 요격 시스템, 하나의 축에서 최소한의 교집합 구하기

참고 문서

• Programmers: 요격 시스템

이 문서의 내용

Step 1: 하나의 축에서 교집합 구하기

하나의 축에서 3개의 선 A B C가 있다고 가정합니다.

이때 A B 그리고 A C는 교집합을 형성하지만 B C는 교집합을 형성하지 못합니다.

A B 관계에서 교집합은 B 시작 값 < A 종료 값 && B 종료 값 <= A 시작 값으로 판단합니다.

수식을 단순화하기 위해서 비교 대상이 되는 A B C를 시작 값으로 오름차순 정렬합니다. 예시에서 정렬이 완료되면 A B C 순서로 배열이 생성됩니다.

이제 A와 A 이후에 이어지는 나머지 원소의 교집합은 대상 시작 값 < A 종료 값으로 판단 할 수 있습니다.

문제에서 제공하는 입력 값은 int[][] target 이차원 배열입니다. 배열의 원소 int[]는 원소의 시작 값[0] 종료 값[1]을 저장하고 있습니다.

입력된 배열을 원소의 시작 값[0] 기준으로 오름차순 정렬합니다.

public static int solution(int[][] targets) 
{
	int[][] sorted = Arrays.stream(targets).sorted((lp, rp) -> (lp[0] < rp[0]) ? -1 : 1).toArray(int[][]::new);
}

Step 2: 하나의 축에서 최소한의 교집합 구하기

정렬된 배열을 기준으로 첫 번째 원소부터 교집합이 형성되는지 검사합니다. 이때 기준이 되는 종료 값은 0부터 시작합니다.

교집합이 형성되지 않으면 기준이 되는 종료 값을 현재 원소의 종료 값으로 대입합니다.

int[][] sorted = Arrays.stream(targets).sorted((lp, rp) -> (lp[0] < rp[0]) ? -1 : 1).toArray(int[][]::new);

int answer = 0, currEnd = 0;
for (int i = 0; i < sorted.length; ++i)
{
	int targetBegin = sorted[i][0];
	int targetEnd = sorted[i][1];
			
	if (targetBegin < currEnd) {
    	...
	} else {
		currEnd = targetEnd;
		++answer;
	}
}

코드		비고
Line 3	currEnd = 0	기준이 되는 종료 값은 0부터 시작합니다.
Line 9:10	if (targetBegin > currEnd)	시작 값이 기준 종료 값보다 작다면 교집합을 형성합니다.
Line 11:14	currEnd = targetEnd	교집합을 형성하지 못하면 현재 원소를 기준으로 합니다.
	++answer	현재 원소가 기준이 되면 1개의 교집합이 생성됩니다(자기 자신).

예를 들어 두 개의 원소 A B가 있으나 어떠한 교집합도 형성하지 못하는 경우는 다음과 같습니다.

만약 교집합을 형성할 수 있다면 기준 종료 값은 두 원소에서 작은 값을 사용합니다. 교집합이 형성될 때마다 교집합의 크기는 축소되기 때문입니다.

교집합의 수는 기준이 변경될 때 카운팅되므로 교집합이 형성된 원소에서는 카운팅하지 않습니다.

int[][] sorted = Arrays.stream(targets).sorted((lp, rp) -> (lp[0] < rp[0]) ? -1 : 1).toArray(int[][]::new);
		
int answer = 0, currEnd = 0;
for (int i = 0; i < sorted.length; ++i)
{
	int targetBegin = sorted[i][0];
	int targetEnd = sorted[i][1];
			
	if (targetBegin < currEnd) {
		currEnd = Math.min(currEnd, targetEnd);
	} else {
		currEnd = targetEnd;
		++answer;
	}
}

코드		비고
Line 10	currEnd = Math.min(currEnd, targetEnd)	교집합이 형성되면 교집합의 크기를 축소시킵니다.

예를 들어 두 개의 원소 A B가 있으며 교집합을 형성하는 경우는 다음과 같습니다.

Step 3: 전체 코드

배열을 정렬하고 두 원소 간의 교집합을 계산하기 위한 수식을 단순화합니다.배열은 원소의 시작 값으로 오름차순 정렬되어있습니다.

첫 번째 원소부터 시작해서 마지막 원소까지 교집합이 형성되는지 검사합니다. 만약 교집합이 형성되지 않으면 기준 종료값은 현재 원소의 것으로 피봇됩니다.

import java.util.*;

public class Solution
{
	public int solution(int[][] targets) {
		int[][] sorted = Arrays.stream(targets).sorted((lp, rp) -> (lp[0] < rp[0]) ? -1 : 1).toArray(int[][]::new);
		
		int answer = 0, currEnd = 0;
		for (int i = 0; i < sorted.length; ++i)
		{
			int targetBegin = sorted[i][0];
			int targetEnd = sorted[i][1];
			
			if (targetBegin < currEnd) {
				currEnd = Math.min(currEnd, targetEnd);
				continue;
			} else {
				currEnd = targetEnd;
				++answer;
			}
		}
		
		return answer;
	}
}