[Python] 프로그래머스 - 체육복

출처: 프로그래머스 코딩 테스트 연습
https://programmers.co.kr/learn/courses/30/lessons/42862

level 1 문제지만 푸는 데 오랜 시간이 걸렸다. 일단 lost 리스트와 reserve 리스트의 중복된 부분을 미리 없애야 하는데, 그때그때 겹치는 부분을 없애는 방식으로 구현하려고 하느라 많은 시간이 걸렸다. 두 리스트의 중복 부분을 우선 없애기로 한 뒤에는, 이를 제대로 구현하지 못해서 또 시간이 소요되었다.

잘못된 접근 방식

def solution(n, lost, reserve):
    for x in lost:
        if x in reserve:
            lost.remove(x)
            reserve.remove(x)

    count = n - len(only_lost)

    for x in lost:
        if x - 1 in reserve:
            reserve.remove(x - 1)
            count += 1
        elif x + 1 in reserve:
            reserve.remove(x + 1)
            count += 1

    return count

위 코드의 문제 = lost 리스트를 for 반복문으로 순회하는 도중에 lost의 요소를 삭제하면, 모든 요소를 제대로 순회하지 못하게 된다. 예를 들어, 3번째 요소를 순회할 때 그 요소를 삭제하면, 다음에 4번째 요소를 뛰어넘고 바로 5번째 요소부터 순회를 이어가게 된다.

나의 최종 풀이

def solution(n, lost, reserve):
    
    only_lost = [x for x in lost if x not in reserve]
    only_reserve = [x for x in reserve if x not in lost]
            
    count = n - len(only_lost)
            
    for x in only_lost:
        if x - 1 in only_reserve:
            only_reserve.remove(x - 1)
            count += 1
        elif x + 1 in only_reserve:
            only_reserve.remove(x + 1)
            count += 1
                
    return count

리스트 컴프리헨션을 통해 리스트의 차집합을 구현했다. [x for x in A if x not in B] 구문은 A 리스트의 요소 중 B 리스트에 없는 요소만으로 이루어진 리스트를 반환한다.

더 나은 풀이

출처 : https://rain-bow.tistory.com/entry/Python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%B2%B4%EC%9C%A1%EB%B3%B5

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)

내 풀이보다 나은 점

1. 리스트의 차집합 구현 - 리스트 컴프리헨션 대신 리스트를 set으로 만든 뒤, 차집합(-) 연산 기호를 사용했다.
2. lost 리스트를 순회하면 순회 시마다 lost 리스트와 reserve 리스트에 모두 연산이 필요하다. 하지만 reserve 리스트를 순회하면 lost 리스트에만 연산이 요구된다.

정리 - 리스트의 차집합 구현하는 방법

1) 두 리스트의 자료형을 셋(set)으로 만든 뒤, 차집합 연산 기호 사용하기

a = [1, 3, 5, 7, 9]
b = [2, 3, 5, 8]

a_sub_b = set(a) - set(b)

2) 리스트 컴프리헨션 활용하기 - [x for x in A if x not in B]

a = [1, 3, 5, 7, 9]
b = [2, 3, 5, 8]

a_sub_b = [x for x in a if x not in b]