[Python] 체육복

코딩테스트 연습 - 체육복

 

요점

이 문제에서 키포인트는 세 가지가 있다. 문제에서 이 세 가지의 키포인트만 잘 찾아낸다면 쉽게 풀 수 있다.

첫 번째로는 체육복을 도난당한 학생, 여벌의 체육복을 가져온 학생 수는 중복되는 번호가 없고,

두 번째로는 여벌 체육복을 가져온 학생도 체육복을 도난당했을 수 있다는 점, 

마지막 세 번째로는 여벌 체육복을 가져온 학생이 자신 기준 왼쪽의 학생부터 주어야 한다는 점이다. 

 

첫 번째 경우로는 lost[2,2,4], reserve[1,3,3,5]와 같은 경우는 없다는 것.

두 번째 경우로는 lost[2,3,4], reserve[1,3,5]와 같은 경우를 보자면 3번 학생은 여벌의 체육복을 가져왔음과 동시에 한 벌을 도난 당했다. 문제에서 하나만 도난당했고 남은 체육복을 하나라고 가정한다고 했다. 3번 학생은 자신이 입을 한 벌의 체육복 밖에 없기 때문에 다른 사람에게 빌려줄 수 없다.

 

첫 번째, 두 번째 경우를 생각해보면 lost, reserve는 중복값이 없는 집합으로 하면 된다는 것을 알 수 있다.

중복값이 없는 집합하면 set을 떠올리면 된다. set은 자신의 요소들 중 중복값을 허용하지 않는 자료구조이다. 그리고 python의 list는 리스트 간의 - 연산을 허용하지 않는데 set은 그것이 가능하다. 이를 이용해서 lost, reserve를 서로 차집합한다. 이때, 각 집합의 요소들에는 영향을 미치지 않는다.

 

set_reserve = set(reserve) - set(lost)
set_lost = set(lost) - set(reserve)

 

이제 누가 누구에게 체육복을 줄지만 결정하면 문제 풀이는 끝난다. 그것에 대한 아이디어는 세 번째 아이디어로 해결이 가능하다.

만약 2,4 학생이 체육복을 잃어버렸고 1,3,5 학생이 여분의 체육복을 가져왔다고 가정해보자. 이 상황에서 여분의 체육복을 가져온 학생들은 자신의 오른쪽 학생부터 옷을 빌려주기로 결정했다. (i+1 번의 학생부터) 과정을 반복한다면 3번 학생은 4번 학생에게 옷을 빌려주고 끝이난다. 5번 학생은 4번 학생에게 옷을 빌려줄 수 있지만 이미 3번에게서 옷을 받았기 때문에 빌려줄 수 없다. 이렇게 된다면 2번은 3번에게서 옷을 빌려받을 수 있지만 못 받게 되므로 적절하지 않다. 즉 여기서, 여벌의 체육복을 가져온 학생들은 자기 자신 기준 왼쪽(i-1)의 학생에게 옷을 빌려줘야 한다는 것을 알 수 있다. 전체 코드를 보면서 이해해보자.

 

def solution(n, lost, reserve):
	set_reserve = set(reserve) - set(lost)
    set_lost = set(lost) - set(reserve)
    for i in set_reserve:
    	if i-1 in set_lost:
        	set_lost.remove(i-1)
        elif i+1 in set_lost:
        	set_lost.remove(i+1)
    
    return n-len(set_lost)