[프로그래머스] 요격 시스템 (Python)

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/181188

프로그래머스

소스 코드

def solution(targets):
    answer = 0
    targets.sort(key=lambda x: x[1]) # end 기준으로 정렬

    s = e = 0

    for start,end in targets:
        if start >= e: # 현재 시작점이 선이 끊기는 점 이후에 위치하는 경우
            answer += 1 # 새로 선 그으며 업데이트
            e = end 

    return answer

해설

• 구현

결과적으로 놓고 보면 굉장히 간단한 코드이지만 아이디어를 떠올리는 것이 굉장히 어려운 문제였던 것 같습니다.

뒤의 숫자를 기준으로 정렬을 수행하는 것도 그렇고, 조건문을 설정하는 것도 쉽지 않은 것 같습니다.

 

가장 중요한 아이디어는 다음과 같습니다.

1. 앞에서부터 하나씩 살펴본다.

2. 현재 살펴보는 시작점이 이전에 확인한 끝점 이후에 존재하는 경우 새로 시작한다.

 

말로는 잘 와닿지가 않아서 숫자로 생각해보면 조금 낫습니다.

뒤의 숫자, 즉 끝나는 지점을 기준으로 정렬하면 첫 번째 원소는 [1,4]입니다.

두 번째 원소는 [4,5], 세 번째 원소는 [3,7]이 될 것입니다.

 

우선 [1,4]를 만나게 되면서 카운트가 하나 올라가고, 이때 끝점이 4가 됩니다.

다음으로 [4,5]를 보면 끝점 이후에 새로 시작되는 것을 알 수 있습니다.

즉 이전의 것과 겹치지 않기 때문에 새로 카운트를 해줘야 합니다.

그래서 이때 answer += 1이 되고, 현재 끝점은 5로 업데이트 됩니다.

 

다음은 [3,7]인데 현재 끝점은 5이고 3은 이것보다 작으므로 업데이트 하지 않습니다.

왜냐하면 이렇게 끝점 이전에 시작하는 경우엔 '한 번에 요격이 가능'하기 때문입니다.

 

하나만 더 살펴보면 다음은 [4,8]입니다.

이번에도 역시 끝점이 5로 업데이트 되지 않은 상태로 유지됩니다.

시작점이 4인 경우 끝점이 5인 경우를 처리할 때 한 번에 요격이 가능하기 때문이죠.

 

이를 끝까지 반복하면 결국,

내장 함수를 이용하여 정렬하는 데 걸리는 시간 O(NlogN)과,

for문에서의 상수 시간 O(N)이 소요되는 것을 알 수 있습니다.

targets의 범위는 500,000까지이므로 이를 만족하는 풀이 방법임을 짐작할 수 있습니다.