문제
이와 아주 비슷한 문제가 광주 인공지능 사관학교 선발 시험에 나왔었다. 당시에는 다른 방법이 생각나지 않아 그냥 그리디로 풀었다.
분류
그리디
코드
def solution(n, lost, reserve):
reserve_set = set(reserve) - set(lost)
lost_set = set(lost) - set(reserve)
for i in reserve_set:
if i - 1 in lost_set:
lost_set.remove(i - 1)
elif i + 1 in lost_set:
lost_set.remove(i + 1)
return n - len(lost_set)
print(solution(5, [2, 4], [1, 3, 5]), 5)
print(solution(5, [2, 4], [3]), 4)
print(solution(5, [1, 2, 4, 5], [2, 3, 4]), 3)해설
프로그래머스에서는 난이도 1이라고 책정하고 있지만 아주 편하지는 않은 문제였다. 생각보다 긴 문제가 부담스러웠고, 그리디를 왜 써도 되는지, 그리고 체육복을 자기 앞뒤로 빌려 줄 수 있는데 앞에 사람한테 빌려줘야하는지 뒤에사람한테 빌려줘야하는지 판단하기 어려웠다.
우선 문제에서 주의해야할 점이 있다.
여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.
즉 예를 들어 x가 여벌을 가져오고 그 여벌을 도난당한 경우, x가 x-1이나 x+1에게 얻어입고 자신의 옷을 다른 사람에 주는 경우를 생각할 필요가 없다. 그래서 set에서 차집합을 이용해 순수하게 잃어버린 사람과 순수하게 여벌을 가진사람만 분류를 한 것이다.
그럼 남은 것은 x가 여벌이 있을 때, x-1에게 빌려줄 것인가 또는 x+1에게 빌려줄 것인가이다.
만약 n=5, lost = [2, 4], reserve = [3, 5]인 경우를 생각해보면,
3은 2와 4 둘 다에게 빌려줄 수 있지만 4에게 빌려주면 2는 옷을 못받는다. 3이 2에게 빌려주면 4는 5에게 옷을 받을 수 있다.
2 4 : lost
3 5 : reserve화살표 방향이 가능하면 왼쪽 위로 향하게 먼저 확인해보고 안되면 오른쪽 위로 하면되는 것이다. 왜 오른쪽 위를 먼저 확인하면 안되는지는 reserve에 마지막 수가 lost의 마지막 수보다 더 클 수 있기 때문이다. 그래서 가능한 reserve 자원을 모두 사용하려면 우선 작은 쪽에 갈 수 있나 확인을 해야한다.
요약하면자신보다 작은 숫자에 옷이 필요한지 확인하고, 있으면 주고 없으면 자기보다 큰 숫자에게 주면 된다.
