[boj 2109.python] 백준 '순회강연' 풀이 (파이썬 런타임에러(ValueError) 해결)

https://www.acmicpc.net/problem/2109

문제 접근

처음에 'd일 안에 와서 강연을 해 주면' 이 문장 때문에 문제 이해에 약간 시간을 썼다. 나와 비슷한 처지(?)에 있으신 분들에게 이해가 쉽도록 예시를 들어드리자면 .. 3개의 대학에서 아래와 같은 조건으로 강연 요청을 해 온 상황이라고 가정 해보자.

 

 

최대로 많은 금액의 강연료를 벌 수 있도록 강연 일정을 최적화할 수 있게 그리디 알고리즘으로 접근했다. 주요 로직은 아래와 같다.

 

1. 강연료가 비싼 순서대로 (p가 큰 순서대로) 정렬한다. 가장 높은 보상을 우선으로 배정하기 위함이다.

2. 위에서 정렬한 것을 기반으로, 가장 큰 강연료를 주는 요청부터 가능한 날짜(d)에 배정한다.

3. 배정 기준은, 날짜를 거꾸로 탐색해서 가장 가까운 가능한 날짜에 배정할 수 있도록 한다.

 

1차 풀이 👉 실패 ❌, 런타임 에러 발생

위의 로직을 기반으로 코드를 짰다.

n = int(input()) # 학교의 수
requests = [tuple(map(int, input().split())) for _ in range(n)] # 요청

def max_speech_fee(n, requests):
    # 강연 요청을 강연료 기준 내림차순 정렬
    requests.sort(key=lambda x: -x[0])
  
    # 최대 날짜를 기준으로 강연 가능 여부 관리
    max_day = max(request[1] for request in requests)
    schedule = [False] * (max_day + 1)  # 각 날짜의 강연 여부
    
    total_fee = 0
    # 강연 요청 처리
    for p, d in requests:
        # d부터 거꾸로 탐색하며 가능한 날짜 찾기
        for day in range(d, 0, -1): # d 부터 거꾸로 탐색
            if not schedule[day]:
                schedule[day] = True
                total_fee += p
                break # 강연을 배치했으므로, 더 탐색할 필요 없이 종료
    print(total_fee)

max_speech_fee(n, requests)

 

강연 가능 여부를 관리할 수 있는 schedule 리스트를 만들고, False로 초기화 한 다음 날짜를 거꾸로 탐색해서 schedule 배열에 넣어주고 True 처리 (해당 날짜에 강연을 배치 했다는 말) 해주는 로직이다.

처음엔 우선순위큐를 사용해서 풀어볼까 했으나, 리스트와 정렬만으로도 코드가 꽤 간단히 풀이가 가능해서 굳이 우선순위큐는 사용하지 않기로 했다.

 

IDE로 풀어가면서 할 때는 모든 예제가 올바른 답을 뱉어내서 당연히 백준에서도 제출이 잘 될 줄 알고 자신만만하게 돌려봤는데 ,, 결과는

ㅋㅎㅋㅎ ★ 런타임 에러 ★

 

원인 분석

런타임 에러가 나는 이유가 뭘까 ..? 짱구를 굴려봤는데 이 부분이 문제라고 판단했다.

max_day = max(request[1] for request in requests)

 

엣지 케이스를 생각 못 했던 것이다.

예를 들면, 입력으로 주어진 강연 요청이 없으면 (n == 0 인 경우) requests 리스트가 비어 있게 된다.

검색해 본 결과, 비어있는 리스트에서 max()를 호출하면 ValueError: max() arg is an empty sequence 에러가 발생한다고 한다.

 

그래서 max_day 변수의 값을 항상 문제의 최대값인 10,000으로 고정해보기로 했다. 

 

2차 풀이 👉 성공 ⭕

n = int(input()) # 학교의 수
requests = [tuple(map(int, input().split())) for _ in range(n)] # 요청

def max_speech_fee(n, requests):
    # 강연 요청을 강연료 기준 내림차순 정렬
    requests.sort(key=lambda x: -x[0])

    # 최대 날짜를 기준으로 강연 가능 여부 관리
    max_day = 10000 	# 이 부분 수정 !!!!!!!!!!
    schedule = [False] * (max_day + 1)  # 각 날짜의 강연 여부
   
    total_fee = 0
    # 강연 요청 처리
    for p, d in requests:
        # d부터 거꾸로 탐색하며 가능한 날짜 찾기
        for day in range(d, 0, -1): # d 부터 거꾸로 탐색
            # print(day)
            if not schedule[day]:
                schedule[day] = True
                total_fee += p
                break # 강연을 배치했으므로, 더 탐색할 필요 없이 종료
    print(total_fee)

max_speech_fee(n, requests)

통과됐다 .. ^-^

 

또 다른 방법

만약 최대 날짜(max_day)를 고정된 값으로 설정하는 방식이 맘에 안든다면 이렇게도 할 수 있다.

n = int(input()) # 학교의 수
requests = [tuple(map(int, input().split())) for _ in range(n)] # 요청

def max_speech_fee(n, requests):
	# 엣지케이스 처리
    if n == 0:
        print(0)
        return
    # 강연 요청을 강연료 기준 내림차순 정렬
    requests.sort(key=lambda x: -x[0])

    # 최대 날짜를 기준으로 강연 가능 여부 관리
    max_day = max(request[1] for request in requests)
    schedule = [False] * (max_day + 1)  # 각 날짜의 강연 여부

    total_fee = 0
    # 강연 요청 처리
    for p, d in requests:
        # d부터 거꾸로 탐색하며 가능한 날짜 찾기
        for day in range(d, 0, -1): # d 부터 거꾸로 탐색
            # print(day)
            if not schedule[day]:
                schedule[day] = True
                total_fee += p
                break # 강연을 배치했으므로, 더 탐색할 필요 없이 종료
    print(total_fee)

max_speech_fee(n, requests)

 

max_day를 기반으로 schedule 배열 크기를 동적으로 설정하는 맨 첫 번째 코드 로직과 동일한데, 입력 n이 0일 경우 예외처리를 if 문으로 해 준 코드이다. 

두 방법의 시간 차이는 거의 안나서, 마음에 드는 걸로 하면 될 듯 🍀

 

느낀 점

항상 엣지케이스를 생각해가면서 코드를 짜자. 입력 데이터의 최소 최대값을 항상 유념하고 있을 것 !!