문제 링크
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까지이므로 이를 만족하는 풀이 방법임을 짐작할 수 있습니다.
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 연속된 부분 수열의 합 (Python) (0) | 2023.05.27 |
---|---|
[프로그래머스] 두 원 사이의 정수 (Python) (0) | 2023.05.18 |
[프로그래머스] 덧칠하기 (Python) (0) | 2023.05.13 |
[프로그래머스] 공원 산책 (Python) (0) | 2023.05.12 |
[프로그래머스] 추억 점수 (Python) (0) | 2023.05.11 |