[프로그래머스 | 파이썬] 체육복

문제 링크

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

풀이

1. 첫 번째 시도
   lost 를 기준으로 체육복을 잃어버린 학생의 앞, 뒤 번호가 reserve 배열에 있는지 확인하고 제거해주었다.
   70점으로 실패!

2. 제한사항중 5번 - 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.
   이 부분을 놓친 것 같아서, lost, reserve에 둘다 포함된 번호를 지워주는 코드를 추가했다.
   그러나 점수는 더 떨어짐.. 문제가 뭘까..

3. 다른 분의 코드를 참고해 로직 방향을 바꿔보았다.
   (중복을 제거한 상태에서) lost 를 기준으로 하지 않고, reserve를 기준으로 해서 여벌체육복을 가진 학생의 앞, 뒤 번호가 lost 배열에 있는지 확인한 후 lost 배열의 원소를 지워주는 것!
   18, 20번만 제외하면 모두 통과했다.

4. 정렬을 해 주면 풀린다는 글을 보고, 두 배열을 우선 정렬해주었다.

def solution(n, lost, reserve):
    _reserve = sorted([r for r in reserve if r not in lost])
    _lost = sorted([l for l in lost if l not in reserve])

    for r in _reserve:
        f = r - 1
        b = r + 1
        if f in _lost:
            _lost.remove(f)
        elif b in _lost:
            _lost.remove(b)

    return n - len(_lost)

음..풀렸다? ㅎㅎ
또는 set 으로 차집합을 구해서 for 문을 돌려도 통과된다. set 을 취하면 정렬되는 효과가 있기에 동일한 로직으로 동작한다.

def solution(n, lost, reserve):
    _reserve = set(reserve) - set(lost)
    _lost = set(lost) - set(reserve)

    for r in _reserve:
        f = r - 1
        b = r + 1
        if f in _lost:
            _lost.remove(f)
        elif b in _lost:
            _lost.remove(b)
            
    return n - len(_lost)

그런데 아직 정렬이 안 된 경우 통과하지 못하는 이유를 잘 모르겠다!!

해결

질문하기에서 반례를 찾다가 발견!!!

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

을 넣어보면, 1은 2에게, 3은 4에게, 5는 6에게 빌려주면 되기 때문에 정답은 6이 나와야 하지만 정렬 없는 코드에서는 5가 나온다!
reserve 를 돌면서 앞/뒤 번호를 lost 에서 찾을 때, 앞 번호를 찾은 다음 뒷 번호를 찾기 때문에, 6에게 체육복을 빌려주어야 하는 5는 4에게 먼저 빌려줘버리고 만다. 이렇게 되면 3은 6에게 빌려줄 수 없기 때문에 6은 체육복을 입을 수 없게 되는 것이다.

즉, 앞 번호(작은 번호)를 먼저 찾는 경우라면 배열들이 모두 오름차순 정렬(점점 커지도록)되어있어야 하고
뒷 번호(큰 번호)를 먼저 찾는 경우라면 배열들이 모두 내림차순 정렬(점점 작아지도록)되어 있어야 한다.

def solution(n, lost, reserve):
    _reserve = [i for i in reserve if i not in lost]
    _reserve.sort(reverse=True)
    _lost = [i for i in lost if i not in reserve]
    _lost.sort(reverse=True)
    
    for r in _reserve:
        b = r + 1
        f = r - 1
        if b in _lost:
            _lost.remove(b)
        elif f in _lost:
            _lost.remove(f)
            
    return n - len(_lost)