Codility] MaxNonoverlappingSegments

Algorithm › Codility
Codility

Lession16. MaxNonoverlappingSegments

Greedy algorithms

A 배열에는 시작점이 들어가 있고, B 배열에는 끝점이 들어가 있다.

주어진 갯수만큼 선들이 있으며, 겹치지 않고 가질 수 있는 최대의 갯수를 구하는 문제이다.

해결 소스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def solution(A, B):
    N = len(A)
    if N == 0: return 0
    if N == 1: return 1
    LINE = []
    for i in range(N):
        LINE.append([A[i], B[i]])

    LINE.sort(key=lambda x: (x[1], x[0]))

    end_point = LINE[0][1]
    cnt = 1
    
    for i in range(1, N):
        if end_point < LINE[i][0]:
            end_point = LINE[i][1]
            cnt += 1
    
    return cnt

소스 설명

범위 설정

1
2
3
N = len(A)
if N == 0: return 0
if N == 1: return 1

배열의 크기가 선의 갯수이기에 N을 만들었다.

N의 범위는 0 <= N <= 30,000이므로 0일 때는 갯수가 0, 1일 때는 갯수가 1이기에 바로 처리해주었다.

바로 처리해주지 않고 아래로 내려가면 인덱스 오류가 발생한다.

Sorting

1
2
3
4
for i in range(N):
	LINE.append([A[i], B[i]])
        
LINE.sort(key=lambda x: (x[1], x[0]))

탐욕적으로 생각해보았을 때 최대의 갯수만 가지면 된다.

시간복잡도를 고려, 라인의 끝점이 작으면서 시작점이 작은 순으로 정리한 후에 처리하면 된다고 생각하였다.

sort함수를 이용하여 끝점을 처음 기준, 다음은 시작점을 기준으로 정렬해주었다.

갯수 세기

1
2
3
4
5
6
7
end_point = LINE[0][1]
cnt = 1

for i in range(1, N):
    if end_point < LINE[i][0]:
        end_point = LINE[i][1]
        cnt += 1

가장 먼저 온 라인이 가장 작을 것이므로 갯수를 하나 증가시키며, 끝점으로 잡아준다.

이제 for문을 통해 그 다음 라인부터 확인하며 시작점이 현재 내가 가지고 있는 끝점보다 클 경우에는 갯수를 증가시키며 끝점을 바꿔준다.

그렇게 다 돌고 난 후 return cnt를 하면 완성