Codility : Greedy MaxNonoverlappingSegments 풀이 Java, Greedy 알고리즘

문제

MaxNonoverlappingSegments coding task - Learn to Code - Codility

 

Located on a line are N segments, numbered from 0 to N − 1, whose positions are given in arrays A and B.

For each I (0 ≤ I < N) the position of segment I is from A[I] to B[I] (inclusive).

The segments are sorted by their ends, which means that B[K] ≤ B[K + 1] for K such that 0 ≤ K < N − 1.

무조건 뒤에 나오는 선의 '끝점'은 앞의 선들보다 뒤에 있다. (아래 그림 참고)

Two segments I and J, such that I ≠ J, are overlapping if they share at least one common point.

In other words, A[I] ≤ A[J] ≤ B[I] or A[J] ≤ A[I] ≤ B[J].

두 선의 시작점은 누가 앞에 있든 상관 없지만 끝점은 무조건 뒤에 나온 선의 끝점이 더 뒤에있다.

We say that the set of segments is non-overlapping if it contains no two overlapping segments.

The goal is to find the size of a non-overlapping set containing the maximal number of segments.

For example, consider arrays A, B such that:

A[0] = 1 B[0] = 5

A[1] = 3 B[1] = 6

A[2] = 7 B[2] = 8

A[3] = 9 B[3] = 9

A[4] = 9 B[4] = 10

A를 시작점, B를 끝점으로 찍으면 아래 선이 된다.

The segments are shown in the figure below.

The size of a non-overlapping set containing a maximal number of segments is 3.

For example, possible sets are {0, 2, 3}, {0, 2, 4}, {1, 2, 3} or {1, 2, 4}. There is no non-overlapping set with four segments.

겹치지 않는 선 번호들의 집합이다. 0과 1은 겹쳐지기 때문에 한 set에 있을 수 없고 3과 4도 마찬가지로 한 set에 있을 수 없다.

겹치지 않는 선의 최대 갯수는 3개이다. 그래서 답은 3 !

 

Write a function:

class Solution { public int solution(int[] A, int[] B); }

that, given two arrays A and B consisting of N integers, returns the size of a non-overlapping set containing a maximal number of segments.

For example, given arrays A, B shown above, the function should return 3, as explained above.

Write an efficient algorithm for the following assumptions:

         N is an integer within the range [0..30,000];

• each element of arrays A and B is an integer within the range [0..1,000,000,000];
• A[I] ≤ B[I], for each I (0 ≤ I < N);
• B[K] ≤ B[K + 1], for each K (0 ≤ K < N − 1).

 

 

그리디 알고리즘을 사용하기 위한 조건

1) 탐욕 선택 속성 (Greedy Choice Property) : 이전의 선택이 이후에 영향을 주지 않는다.

2) 최적 부분 구조 (Optimal Substructure) : 부분 문제의 최적 결과가 전체에도 그대로 적용될 수 있어야 한다.

 

반례를 1개만 찾아도 그리디가 아님을 증명할 수 있는데 위 문제에서는 반례를 찾을 수 없었다.

 

그리디 알고리즘의 대표적인 예시가 활동 선택(Action Selection) 이다.

N 개의 활동이 있고 각 활동의 시작 종료 시간이 있으며 한 사람이 최대한 많이 할 수 있는 활동의 수를 구하는 문제이다.

-> 가장 종료시간이 빠른 것부터 선택하고 다음에 선택 가능한 활동을 찾아서 수행하면 된다. (종료시간이 빠른걸 계속 선택함)

 

그리디 알고리즘은 항상 최적의 선택은 아니다. 하지만 위 조건이 성립할 때에 사용하면 빠르게 접근이 가능하다.

 

 

 

 

해답

핵심은 문제에 적힌 아래 조건이다. 뒤에 나오는 선들은 무조건 앞에 선보다 끝나는 점이 뒤에 있기 때문에 그리디 적용이 가능하다.

즉, 조건만 맞다면 선을 포함하는 방식으로 그리디 알고리즘을 적용하면 답이 나온다.

만약 이런 조건이 없었다면 이중포문으로 모든 점들을 시작점으로 하고 그리디 알고리즘을 돌려야 하는데..(시간초과 뜸)

 

포문 하나로 문제 해결이 가능한 이유는

위에 나온 그림을 다시 한번 보자.

0과 1은 중복이기 때문에 무조건 둘 중 하나만 사용해야 하고, 3과 4도 중복이기 때문에 무조건 둘 중 하나만 사용해야 한다.

그렇게 되면 크게 (0,1) 2 (3,4) 3개의 그룹으로 묶이게 되며, 결과는 3이 된다.

이런 조건 때문에 순서 상관없이 조건에 맞으면 선을 포함하는 방식으로 진행한다.

 

B[K] ≤ B[K + 1], for each K (0 ≤ K < N − 1).

class Solution {
    public int solution(int[] A, int[] B) {
		int N = A.length;
		int res = 1;

        if(N<=1)
            return N;

        int start=0;
		for (int i = 1; i < N; i++) {

			if (B[start] < A[i]) {
				res++;
				start = i;
			}
		}
		return res;
	}
}

 

 

 

References

https://hongjw1938.tistory.com/172