[백준 / Python] #3985 롤 케이크

3985번: 롤 케이크

첫 번째 시도

---

L = int(input()) # 롤 케이크의 길이
N = int(input()) # 방청객의 수
li = list() # 기대하는 조각의 길이 리스트
d = dict() # 실제 차지한 조각 딕셔너리
for guest in range(1, N+1):
    p, k = map(int, input().split()) # 종이에 적어낸 조각의 범위
    li.append(k - p)
    for i in range(p, k+1):
        d[i] = 0
        if d[i] in range(1, N+1):
            print("pass")
            continue
        else:
            d[i] = guest

print(li.index(max(li)) + 1) # 가장 많은 조각을 받을 것으로 기대하고 있던 방청객의 번호
print(d)

# 실제 차지하는 조각은 딕셔너리 타입을 이용하여 각 플레이어별로 체크함

가장 많은 조각을 받을 것으로 기대하는 방청객 번호는 리스트를 생성하여 각 방청객별로 희망하는 롤케이크의 길이를 담아서 가장 긴 값을 출력하고자 했다.

그리고 실제로 많은 조각을 받는 방청객 번호는 딕셔너리를 생성하여 조각 인덱스를 key, 방청객 번호를 value로 먹여서 구분해두고, 만약 딕셔너리에 key, value를 입히는 과정에서 이미 value가 존재하는 key의 경우에는 pass 하도록 구성하였다.

위 코드의 결과는 실패이고, 문제점을 파악하기 위해 테스트를 돌려본 결과,

아래 코드가 의도대로 동작하고 있지 않고 있었다.

for i in range(p, k+1):
        d[i] = 0
        if d[i] in range(1, N+1):
            print("pass")
            continue
        else:
            d[i] = guest

위 코드 중에서 특히 아래 코드가 문제인 것으로 파악되었는데,

if d[i] in range(1, N+1):
    print("pass")
    continue

위 코드를 통해 내가 구현하고자 했던 효과는 “딕셔너리 내에 기존에 배정된 값이 있다면 넘어가라” 였다. 처음에는 이 코드 위의 d[i] = 0 없이 로직을 구성하였는데, key error(딕셔너리 타입의 변수에 키값이 할당되지 않은 상태에서 그를 호출할 경우 발생하는 에러)가 발생하여 임시방편으로 d[i] = 0을 추가한 결과였다.

위 코드의 문제를 파악하기 위해 케이스별로 머리를 굴려보았다. 다음은 위 코드에서 N == 3 and i == 2일 때의 연산 과정을 한글로 나타낸 것이다.

d[2] = 0이 입력되고,
d[2]가 1부터 3사이에 있다면 pass, 아니면 guest값을 입력

이렇게 풀어 보니 문제가 보인다. d[i] = 0 으로 초기화하고 로직에 들어가니 그 어느 것도 if 문으로 들어갈 수 없는 것이다. 풀어서 생각해보니 어처구니없는 로직이 아닐 수 없다.

재설계의 필요성을 느낀 뒤, 동일한 결과를 딕셔너리 타입의 keys() 내장함수를 이용하여 도출할 수 있을 것 같아 아래와 같이 다시 설계하였다.

---

두 번째 시도

---

L = int(input()) # 롤 케이크의 길이
N = int(input()) # 방청객의 수
li = list() # 기대하는 조각의 길이 리스트
d = dict() # 실제 차지한 조각 딕셔너리
for guest in range(1, N+1):
    p, k = map(int, input().split()) # 종이에 적어낸 조각의 범위
    li.append(k - p)
    for i in range(p, k+1):
        if i in list(d.keys()):
            # print("pass")
            continue
        else:
            d[i] = guest

print(li.index(max(li)) + 1) # 가장 많은 조각을 받을 것으로 기대하고 있던 방청객의 번호
# print(list(d.values()))
result = list()
for guest in range(1, N+1):
    result.append(list(d.values()).count(guest))
print(result.index(max(result))+1)

딕셔너리의 키 값이 초기화되어 있다는 의미는 그 전에 배정받은 값이 있다는 말, 즉 이미 케이크를 받은 방청객이 있음을 의미한다고 판단하였다. 따라서 문제의 코드를 아래와 같이 수정하였다.

for i in range(p, k+1):
    if i in list(d.keys()):
        # print("pass")
        continue
    else:
        d[i] = guest

위 과정을 통해 딕셔너리에는 각 케이크 조각 별로 어떤 청중이 받는지 key, value로 매핑되어 있다. 따라서 이제는 d.values() 를 확인하여 어떤 청중의 번호가 가장 많은지를 체크하면 누가 실제로 가장 많은 조각을 가져가는지 확인할 수 있을 것이다.

가장 많은 조각을 가져가는 청중의 카운트값을 result라는 리스트에 입력하는데, 이 때 청중 번호를 순서대로 리스트에 입력함으로써 그 인덱스 값이 청중의 번호를 의미하게끔 하였다. 결과적으로, “result 리스트 내의 최대값을 지닌 인덱스 값”이 “가장 많은 조각을 차지한 청중의 번호”와 일치하게 된다.

위 과정을 통해 성공하였다.