프로그래머스 코딩테스트 고득점 Kit_탐욕법(Greedy)_단속카메라

문제 보러 가기 👈 클릭!

💡 풀이

✔ 풀이 방법

• 가장 먼저 고속도로를 진입 한 순서대로 정렬

• 로직 👇

1. n번째 차량 진입/진출 구간 pop()
2. 해당 구간과 다음 차량의 구간이 겹치면,
   해당 구간을 겹치는 구간으로 변경하여 다음 차량 구간과 겹치지 않을때 까지 pop() & 겹치는 구간 갱신 반복
3. 겹치지 않을 경우, 다음 차량을 pop()하고 해당 차량 진입/진출 구간으로 갱신

구현 코드 👇

def solution(routes):
    routes.sort(reverse = True) #pop()연산은 오른쪽 값을 제거하므로 내림차순 정렬 
    answer = 0
    while routes:
        answer += 1
        start, end = routes.pop()
        while routes and routes[-1][0] <= end:
            s, e = routes.pop()
            start, end = max(start, s), min(end, e)

    return answer

📝 프로그래머스의 다른 풀이방법

• 진출 구간순으로 정렬
  -> 진출 구간은 해당 차량이 단속카메라를 만날 수 있는 마지막 구간

• 다음 차량이 현재 차량과 겹치는 구간이 있을 경우, 계속 반복
  다음 차량이 현재 차량과 겹치는 구간이 없을 경우, 진출 구간 갱신

• 진출 구간순으로 정렬하였으므로 겹치는 구간이 있는 모든 차량은 기준 차량이 고속도로를 나가기 전까지 나가지 않는다.

다른 풀이 코드👇

def solution(routes):
    answer = 0
    last_camera = float('-inf')
    routes.sort(key=lambda x: x[1]) #진출 순서대로 정렬

    for s, f in routes:
        if s > last_camera: #겹치는 구간 없는 경우
            answer += 1
            last_camera = f

    return answer

문제를 읽고 정확히 그대로 구현하는 방법도 좋지만, 이렇게 똑같은 결과를 내는 센스있는 다른 방법을 생각할 수 있는 힘을 기르고 싶다!