[algorithm][python] 프로그래머스 체육복

문제

프로그래머스 체육복

문제 풀이

def solution(n, lost, reserve):
    for i in reversed(reserve): #체육복 가져왔는데 도난 당한 학생을 각 배열에서 제거
        if i in lost :
            lost.remove(i) 
            reserve.remove(i)
    for i in reserve : # reserve에 속한 학생의 앞, 뒷번호에 해당하는 학생이 lost에 존재하면 제거
        if i - 1 in lost : 
            lost.remove(i-1) 
        elif i + 1 in lost :
            lost.remove(i+1)     
    answer = n-len(lost)
    return answer

문제점 및 해결방안

    for i in reserve :
    	if i in lost :
            lost.remove(i) 
        elif i - 1 in lost : 
            lost.remove(i-1) 
        elif i + 1 in lost :
            lost.remove(i+1)     

맨 처음에 작성한 코드는 위와 같다. 앞 뒷번호 학생을 제거(빌려줌)하는 것과 체육복을 가져왔지만 도난당한 학생을 제거하는 것을 같은 단계의 for문에서 처리했던 것이 문제였다. 따라서 다음과 같이 if문을 맨위로 뺏다.

 for i in reserve:
     if i in lost :
         lost.remove(i) 
 for i in reserve :
     if i - 1 in lost : 
         lost.remove(i-1) 
     elif i + 1 in lost :
         lost.remove(i+1)     

이번에는 다음 테스트케이스를 통과하지 못했다.

solution(5, [2, 3, 4], [1, 2, 3])

이 케이스의 정답은 4인데 내 코드로는 결과로 5가 나왔다. 그 이유는 맨 처음 reserve 원소에서 1이 lost의 2에게 체육복을 빌려주게 되는데, 2는 빌려입지 않고 자신이 가져온 여벌 체육복을 입어야한다. 그런데 이 코드 상으로는 (1->2), (2->3), (3->4) 이렇게 빌려입게된다. 결과적으로 if문을 앞으로 뺐다해도 사전 검사가 아니게된 것이다. 따라서 이 오류를 아래코드와 같이 해결하고자 했다. 체육복을 가져왔지만 도난당한 [2,3]과 같은 친구를 각 배열에서 제거했다.

    for i in reserve:
        if i in lost :
            lost.remove(i)
            reserve.remove(i)
    for i in reserve :
        if i - 1 in lost : 
            lost.remove(i-1) 
        elif i + 1 in lost :
            lost.remove(i+1)     

여기서의 문제점은 리스트의 앞 원소부터 검사를 시작하는데, 리스트의 끝이 아닌 중간 부분에서 제거되면 제거된 이후의 원소를 한칸 씩 왼쪽으로 이동하기 때문에 원래 인덱스 자리에 있었던 원소에 접근하지 못하게 되는 문제가 발생한다.(출력해서 확인해 봄) 그래서 최종적으로 아래와 같이 코드를 작성했다.

    for i in reversed(reserve):
        if i in reserve(lost) :  
            lost.remove(i)
            reserve.remove(i)
    for i in reserve :
        if i - 1 in lost : 
            lost.remove(i-1) 
        elif i + 1 in lost :
            lost.remove(i+1)     

reverse(일시적으로 역순)를 사용해서 lost 뒷부분의 원소부터 검사를 해서 각 배열의 뒷 부분 원소부터 제거되도록 했다. 원소가 중복되지 않는다는 가정 하에 가능한 일이다.

사실 체육복을 가져왔지만 도난 당한 학생은 lost & reserve(교집합)이기 때문에 set을 사용하는 것이 가독성측면에서 더 좋겠다.

def solution(n, lost, reserve): 
    self = set(lost) & set(reserve) #체육복을 가져왔지만 도난 당한 학생
    lost = list(set(lost) - self) # 각 배열에서 교집합 제거
    reserve = list(set(reserve) - self)
    
    for i in reserve : 
        if i - 1 in lost : 
            lost.remove(i-1) 
        elif i + 1 in lost :
            lost.remove(i+1)     
    answer = n-len(lost)
    return answer