[프로그래머스][Python] 체육복

[프로그래머스][Python] 체육복

https://school.programmers.co.kr/learn/courses/30/lessons/42862#

프로그래머스

 

---

아이디어

defaultdictionary를 만들어서 여분이 있고 lost에 포함되지 않는 번호는 value를 2, 여분이 있지만 도난 당했으면 value 1로 설정해뒀다.

lost 리스트를 돌면서 잃어버린 번호의 앞 번호, 그 다음 뒷 번호를 확인하면서 여분이 있으면 하나씩 나눠 갖도록 코드를 짰다. 여기서 중요한 점은 내 코드는 앞 번호부터 확인했기 때문에 lost 리스트를 정렬한 상태로 진행해야 한다.

그 이유는 n=5, lost=[4,2], reserve=[3,5] 일 때 2번은 3번의 여유분을 갖고 4번은 5번의 여유분을 가지면 answer이 5가 나오고 끝난다. 하지만 정렬을 안 한 상태에서 돌리면 lost 기준으로 앞 번호부터 확인하니까 4번은 3번의 체육복을 빌리게 되고 2번은 결국 체육복을 빌리지 못하게 되어 answer이 4가 나온다.

 

코드 짜다가 막혔던 반례)

n=5, lost=[4,2], reserve=[3,5]

>> answer: 5

 

---

코드

from collections import defaultdict
def solution(n, lost, reserve):
    answer = 0
    dict = defaultdict(int)
    for i in reserve:
        if i not in lost:
            dict[i] = 2
        else:
            dict[i] = 1
    
    lost.sort()
    for i in lost:
        if dict[i] >= 1:
            continue
            
        elif dict[i-1] == 2:
            dict[i] = 1
            dict[i-1] = 1
            
        elif dict[i+1] == 2:
            dict[i] = 1
            dict[i+1] = 1
            
        else: # can't borrow
            answer += 1
        
        
    # n - (체육복 없는 애들)    
    return n - answer