[다시보기] [그리디] - 선긋기

선긋기

한 번의 선긋기는 수직선상의 한 점에서 다른 한 점까지 선을 긋는 것입니다. 선을 그을 때는 이미 선이 있는 위치에 겹쳐서 그을 수도 있습니다.
여러번 그은 곳과 한 번 그은 곳의 차이는 없습니다.
수직선은 0번 지점부터 m번 지점까지의 길이를 갖고 있습니다.

매개변수 nums에 각각의 선긋기 정보가 주어지면 0번 지점부터 m번 지점까지 연속적인 선이 그어지도록 하기 위한 선긋기 최소횟수를 반환하는 프로그램을 작성하세요.
모든 입력은 0번 지점부터 m번지점까지 연속적인 선이 그어집니다.

제한사항:
• 3 <= m <= 10,000
• nums의 길이는 100,000을 넘지 않습니다.
• nums[i][0]은 i번째 선긋기의 시작 점, nums[i][1]은 i번째 선긋기의 끝점입니다. • 0 <= nums[i][0] < nums[i][1] <= 10,000

 

 

 

 

나의 코드 

 

나의 접근법: 

1. 첫 시작적을 정렬

2. 0으로 시작하는 선중 가장 긴 선 [0,3] 찾기

3. 1~3 사이 로 시작하는 선중 가장 긴선 찾기

4. 3번을 반복하다 끝점이 target이면 종료

 

분명 그리디 알고리즘의 로직을 생각하긴 했는데 '구현'하는게 아직 실력이 많이 부족한거같다..아 빡쳐

 

 

정답코드

 

def solution(m, nums):
    answer = 0
    n = len(nums)
    nums.sort(key = lambda v : v[0])
    start = end = i = 0
    while i < n:
        while i < n and nums[i][0] <= start:
            end = max(end, nums[i][1])
            i += 1
        answer += 1
        if end == m:
            return answer
        start = end
            
    return answer
    
                                           
print(solution(12, [[5, 10], [1, 8], [0, 2], [0, 3], [2, 5], [2, 6], [10, 12], [7, 12]]))
print(solution(15, [[1, 10], [0, 8], [0, 7], [0, 10], [12, 5], [0, 12], [8, 15], [5, 14]]))
print(solution(20, [[3, 7], [5, 8], [15, 20], [0, 5], [7, 14], [3, 10], [0, 8], [13, 18], [5, 9]]))
print(solution(30, [[5, 7], [3, 9], [2, 7], [0, 1], [0, 2], [0, 3], [19, 30], [8, 15], [7, 12], [13, 20]]))
print(solution(25, [[10, 15], [15, 20], [5, 15], [3, 16], [0, 5], [0, 3], [12, 25]]))

정답 코드를 보니 시작점과 끝점과 nums의 인덱스를 나타내는 i를 사용하였다.

흠... 로직 구현시 필요한 변수와 반복문 구현을 더 연습을 해야겠다.