프로그래머스 - 탐욕법 - 단속카메라(MJ)

📖Problems : 프로그래머스 - 고득점 kit - 탐욕법(greedy) - 단속카메라

Level3

고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.

고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.

제한사항

• 차량의 대수는 1대 이상 10,000대 이하입니다.
• routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.
• 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.
• 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.

입출력 예

routes	return
[[-20,-15], [-14,-5], [-18,-13], [-5,-3]]	2

입출력 예 설명

• 5 지점에 카메라를 설치하면 두 번째, 네 번째 차량이 카메라를 만납니다.
• 15 지점에 카메라를 설치하면 첫 번째, 세 번째 차량이 카메라를 만납니다.

🔍Approach

🚩첫 시도

def solution(routes):
    answer = 0
    routes.sort()
    point = routes[0][1]

    for i in range(1, len(routes)):
        # 겹치는 경우
        if routes[i][0] <= point:
            answer += 1
        # 안 겹치는 경우
        else:
            point = routes[i][1]

    return answer

→ 주어진 테스트케이스만 통과함, 제출하면 실패한 코드

def solution(routes):
    answer = []
    routes.sort()
    left = routes[0][0]
    right = routes[0][1]
    for i in range(1, len(routes)):
        # 겹치는 경우
        if left < routes[i][0] < right:
            continue
        # 안 겹치는 경우
        else:
            answer.append(right)
            left = routes[i][0]
            right = routes[i][1]

    return len(answer)

→ 이 코드도 마찬가지..

뭐가 문제인걸까…

진짜 어이없다… 아무리해도 코드는 맞는데 계속 틀리길래 뭐가 문제지 했는데 정렬하는게 문제였다.

routes.sort()로 하면 안돼고, lambda를 이용해서 정렬해야 한다. 근데 이게 무슨 차이인가..??

🚩My submission

flow

1. 정렬한다.
2. 최소 -30000이므로 카메라 위치를 -30001로 초기화해둔다.
3. routes 리스트를 반복하면서 카메라가 진입지점(i[0])보다 작은지 확인한다.
4. 만약 작다면, 카메라위치로 차량을 못 만났다는 것을 의미하기 때문에
   1. 카메라를 추가로 세워야 한다. 따라서 answer += 1
   2. 카메라의 위치를 방금 진출지점(i[1])으로 갱신한다.
5. 반복문이 끝나면 카메라의 개수인 answer를 return한다.

def solution(routes):
    answer = 0
    routes.sort() 
    camera = -30001
    
    for i in routes:
        if i[0] > camera:
            camera = i[1]
            answer += 1
    return answer

def solution(routes):
    answer = 0
    routes.sort(key=lambda x: x[1]) 
    camera = -30001
    
    for i in routes:
        if i[0] > camera:
            camera = i[1]
            answer += 1
    return answer

🚩More …

그래서 원래 내가 작성한 코드도 잘 작동하는지 수정해서 확인해보았다.

def solution(routes):
    answer = 0
    routes.sort(key=lambda x: x[1]) 
    point = -30001
    
    for i in range(1, len(routes)):
        # 안 겹치는 경우
        if routes[i][0] > point:
            point = routes[i][1]
            answer += 1

    return answer

여기서 문제가 됐던 건 for문의 범위를 잘못 설정해서이다.

위에서 정답으로 나왔던 것처럼 range를 수정해주면 정답으로 인정이 된다.

def solution(routes):
    
    answer = 0 # 필요한 카메라 수
    routes.sort(key=lambda x: x[1])   # 진출지저에 대해 오름차순 정렬
    camera = -30001 # 제한사항을 토대로 최솟값으로 초기화

    for i in routes:
        # 기존 카메라보다 진입지점이 뒤에 있으면(겹치지 않는다면)
        if i[0] > camera:
            answer += 1 # 단속이 안 되므로 카메라 하나 더 필요함
            camera = i[1]  #새로운 기준으로 갱신
            
    return answer

1. “진출”지점에 대해서 오름차순으로 정렬한다.
2. 기준 = -30001 (문제 제한사항을 고려함)
3. cnt = 0
4. for 경로 in 경로들:
   • 만약 경로의 진입지점이 기준보다 뒤에 있으면,
     • cnt += 1
     • 기준 = 경로의 진출지점
5. return cnt

💡TIL

• 최솟값은 리스트 안에서 가장 첫번째 값을 넣는 것이 아니라 문제 조건에서 차량 진입지점, 진출지점이 -30000~30000으로 주어졌으므로 최솟값으로 초기화할 때는 -30000으로 해야 한다. (당연한건데,, 바보같다)
• 람다Lambda (https://itkjspo56.tistory.com/m/289) (https://mieumje.tistory.com/119)
  • 함수를 하나의 식으로 표현
  • 익명함수라서 이름이 없고, 저장되어 있는 변수가 없어 재사용은 불가능.
  • 일시적으로 쓰이는 함수라서 정의하거나 변수에 저장해 사용하는 것이 아니라 즉시 사용하고 바로 버리는 함수
  • 리스트, 배열 등을 정렬할 때 정렬조건을 람다 함수로 사용하는 경우가 많음

    lambda 매개변수:표현식
    # lambda a:a+1
  

  

  • 람다식(Lambda Expression) 의 특징
    • 람다식 내에서 사용되는 지역변수는 final이 붙지 않아도 상수로 간주된다.
    • 람다식으로 선언된 변수명은 다른 변수명과 중복될 수 없다.
  • 람다식(Lambda Expression) 의 장점
    1. 코드를 간결하게 만들 수 있다.
    2. 식에 개발자의 의도가 명확히 드러나 가독성이 높아진다.
    3. 함수를 만드는 과정없이 한번에 처리할 수 있어 생산성이 높아진다.
    4. 병렬프로그래밍이 용이하다.
  • 람다식(Lambda Expression) 의 단점
    1. 람다를 사용하면서 만든 무명함수는 재사용이 불가능하다.
    2. 디버깅이 어렵다.
    3. 람다를 남발하면 비슷한 함수가 중복 생성되어 코드가 지저분해질 수 있다.
    4. 재귀로 만들경우에 부적합하다.

    → 람다라고 무조건 좋은건 아니다. 상황에 맞게 적절하게 사용하자:)