[프로그래머스] 탐욕법(Greedy) - 체육복 (파이썬)

프로그래머스 탐욕법(Greedy) - 체육복, 문제 확인

1차원적으로 문제를 이해해서는 테스트케이스 중 여러 문제를 통과할 수 없다. 테스트케이스를 알 수 없어 대체 뭐가 문제인지 난항에 빠졌었는데 '질문하기'를 이것저것 찾아보다가 겨우 해결할 수 있었다. 실전에서는 스스로 모든 예외를 생각해봐야 할텐데 아직 그런 스킬이 많이 부족한 것 같다.

 

문제 설명은 아래와 같다.

 

---

일부 학생의 체육복이 도난당함

여벌 체육복이 있는 학생이 체육복을 빌려줄 수 있음

하로 앞번호 학생이나 뒷번호 학생에게만 체육복을 빌려줄 수 있음

최대한 많은 학생이 체육수업을 들을 수 있게 해야 함

여벌 체육복을 가져온 학생이 체육복을 도난당했을 경우 하나만 도난당했다고 가정, 다른 학생에게 빌려줄 수 없음

 

n: 전체 학생 수

lost : 체육복을 도난당한 학생들의 번호가 담긴 배열

reserve: 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열

수업을 들을 수 있는 학생의 최댓값을 리턴

 

 

프로그래머스 탐욕법(Greedy) - 체육복, 문제 풀이 (파이썬)

처음에 문제를 풀고나서 테스트케이스를 확인해보니 3,7,10만 틀렸었다. 이 경우 "여벌 체육복을 가져온 학생이 체육복을 도난당했을 경우 하나만 도난당했다고 가정, 다른 학생에게 빌려줄 수 없음"를 고려하지 않았기 때문이다. 제일 먼저 lost와 reserve 간의 중복을 제거해주어야 한다. 3,7,10 테스트케이스만 계속 틀리게 나오는 사람은 ( n=5, lost=[1,2], reserve=[2,3], return=4 / n=5, lost=[5,4,2], reserve=[2,4], return=4) 와 같은 테스트케이스를 추가해보길 바란다.

 

• n=5, lost=[1,2], reserve=[2,3], return=4

• n=5, lost=[5,4,2], reserve=[2,4], return=4

 

중복을 제거하는 방법에는 여러가지가 있지만, 구글링하다가 set과 intersection을 사용하는 신박한 방법을 찾아서 이 방법을 썼다. 아래와 같이 set(list1).intersection(list2) 를 사용하면 list1과 list2 간의 중복되는 요소에 대한 리스트를 얻을 수 있다. 그리고 중복 요소를 구했으니 해당 요소값을 lost와 reserve에서 제거해준다.

 

def solution(n, lost, reserve):
    common = set(lost).intersection(reserve) # lost,reserve 간 중복 요소 구하기
    for v in common:
        reserve.pop(reserve.index(v)) # 중복 제거
        lost.pop(lost.index(v)) # 중복 제거 
    answer = n-len(lost) # 수업을 들을 수 있는 학생은 일단 n-len(lost)

 

 

이제 lost를 기준으로 체육복을 빌릴 수 있는 상태인지 확인해주는 것이 필요하다. lost 리스트에 대해 반복문을 돌면서 앞번호(v-1)가 reserve 배열에 존재하는지 확인하고 존재한다면 해당 학생은 수업을 들을 수 있게 되는 것이므로 answer를 +1 해주고 빌려준 학생은 이제 다른 학생에게는 빌려주지 못하므로 reserve에서 pop을 해준다. 뒷번호(v+1)가 존재하는 경우도 마찬가지로 수행해준다.

 

    for i,v in enumerate(lost):
        if v-1 in reserve: # 앞번호가 reserve 배열에 존재하는지 확인
            answer+=1
            reserve.pop(reserve.index(v-1)) 
            continue # 이미 빌렸으므로 다음으로 넘어가기
        if v+1 in reserve: # 뒷번호가 reserve 배열에 존재하는지 확인  
            answer+=1
            reserve.pop(reserve.index(v+1)) # 뒷번호가 reserve 배열에 존재하는지 확인  

    return answer

 

 

전체 코드는 아래와 같다.

 

def solution(n, lost, reserve):
    common = set(lost).intersection(reserve) # lost,reserve 간 중복 요소 구하기
    for v in common:
        reserve.pop(reserve.index(v)) # 중복 제거
        lost.pop(lost.index(v)) # 중복 제거 
    answer = n-len(lost) # 수업을 들을 수 있는 학생은 일단 n-len(lost)
    
    for i,v in enumerate(lost):
        if v-1 in reserve: # 앞번호가 reserve 배열에 존재하는지 확인
            answer+=1
            reserve.pop(reserve.index(v-1)) 
            continue # 이미 빌렸으므로 다음으로 넘어가기
        if v+1 in reserve: # 뒷번호가 reserve 배열에 존재하는지 확인  
            answer+=1
            reserve.pop(reserve.index(v+1)) # 뒷번호가 reserve 배열에 존재하는지 확인  

    return answer

 

 

아래와 같이 모든 테스트케이스를 통과하게 된다.