[그리디, 힙] 단속카메라

코딩테스트 연습 - 단속카메라 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 단속카메라

 

 그리디 문제라고는 하지만, 생각만큼 쉽진 않을 것 같다.

포인트는 두개인 것 같다. '최대한 많이겹치는 경로'랑 '모든 경로를 한 번은 지나쳐 가야한다.'

 

 그렇다면, 출발지 기준으로 sort를 한다. heapify가 괜찮을 것 같다.

그리고 맨 처음 경로를 뽑아내 키값으로 만들고, 그 다음 경로들이 키값에 포함되어 있으면 pop을 한다. 

그리고 키값에 포함되어있지 않는 경로가 나올때까지 pop을 한다. 그리고 그 경로가 나왔다면, 그 경로를 새로운 키값으로 하고 같은 행동을 반복한다.

 

 일단 기본 로직은 이렇게 짰는데, 생각해보니 경로가 긴 것을 중심으로 생각하는 것이 아니라 짧은 것을 기준으로 생각해야한다. 그렇다면 경로의 출발 지점이 아닌, 끝 지점을 중심으로 생각해야하는 것인가. 끝 지점을 기준으로 heap 정렬을 했을 때, 키값을 정하고 다음 값의 출발 지점이 키값의 도착 지점보다 짧으면 pop하는 식은 어떨까.

 

통과

 

 깔끔하게 통과했다.

def solution(routes):
    import heapq
    answer = 0
    heapList = []

    for route in routes:
        heapq.heappush(heapList, [route[1], route[0]])

    # heapList = [도착지점, 출발지점]
    while (heapList):
        keyVal = heapq.heappop(heapList)
        answer += 1

        while (heapList and heapList[0][1] <= keyVal[0]):
            heapq.heappop(heapList)
    return answer

 

다시 로직을 정리한다면,

1. 도착 지점을 기준으로 최소 힙정렬을 한다. 

   (코드에서는 [도착 지점, 출발 지점]의 형식으로 새롭게 리스트(heapList)를 만들어서 힙정렬을 했지만 그렇게 멋있는 방법은 아니다. 정석대로라면 [출발 지점, 도착 지점]의 형식에서도 도착 지점을 기준으로 힙 정렬을 구현하는 것이 더 멋진 방법일 것이다. 하지만, 코테라는 것이 시간안에 어떻게든 풀어야 한다는 문제가 있지 않은가...)

 

2. heapList의 첫번째 인자를 pop해 키 값(keyVal)으로 만든다. 이 키 값의 도착지점은 heapList 에서 가장 작은 값의 도착지점을 가진다. 이는 위에서 말한  '모든 경로를 한 번은 지나쳐 가야한다.' 를 만족시키기 위함이다. 이 경로 상의 한 점에 카메라를 설치할 것이니 미리 answer ++을 해주자.

 

3. 키 값을 만든 뒤에, heapList의 첫번째 요소의 출발 지점과 keyVal의 도착 지점을 비교해본다. 즉, 경로가 겹치는지 확인하는 것이다. 겹치지 않는 경로가 나올 때까지 pop을 반복한다.

 

4. 만약 겹치지 않는 경로가 나왔다면, 그 값을 새로운 keyVal로 만들어준다. 즉, 2번 3번 과정을 반복하는 것이다.

 

 

참 쉽죠?

사실 힙 정렬을 알고 쓰느냐에 대한 문제 같았다.

비슷한 문제는 아래와 같다.

13334번: 철로 (acmicpc.net)

코딩테스트 연습 - [1차] 추석 트래픽 | 프로그래머스 (programmers.co.kr)