[PS/Python] 체육복

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

프로그래머스

 

이 문제에서 얻고 가야할 부분

 

1. set() - remove메서드의 낮은 시간 복잡도, 얕은 복사

2. 문제에서 작은 예시를 통해 문제를 이해하자 ->

* 여벌의 체육복을 가져온 사람은 단 한명에게만 체육복을 빌려줄 수 있다.

* 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

def solution(n, lost, reserve):
    
    #lost 체육복 잃어버린 사람
    #reserve 여벌의 체육복을 가져온 사람
    lost_set = set(lost) - set(reserve)
    reserve_set = set(reserve) - set(lost)
    
    #set의 remove는 시간 복잡도가 O(1)
    
    # set은 불변 객체이므로 얕은 복사 기능을 사용해도 됨
    # 단, list와 같은 가변 객체는 얕은 복사 기능을 사용할 때 주의
    for x in lost_set.copy():
        if x-1 in reserve_set:
            lost_set.remove(x)
            #제거
            reserve_set.remove(x-1)
        elif x+1 in reserve_set:
            lost_set.remove(x)
            reserve_set.remove(x+1)
            
    answer = n - len(lost_set)
    return answer

lost_set = set(lost) - set(reserve):

이 코드는 lost 리스트에 있는 학생들 중에서 reserve 리스트에도 있는 학생들을 제거합니다.

즉, 체육복을 도난당했지만 여벌 체육복을 가지고 있는 학생들은 lost_set에 포함되지 않도록 합니다. 이 학생들은 본인의 여벌 체육복을 입을 수 있기 때문입니다.

reserve_set = set(reserve) - set(lost):

이 코드는 reserve 리스트에 있는 학생들 중에서 lost 리스트에도 있는 학생들을 제거합니다.

즉, 체육복을 도난당했지만 여벌 체육복을 가지고 있는 학생들은 reserve_set에 포함되지 않도록 합니다. 이 학생들은 이미 본인의 체육복을 입을 수 있기 때문에 다른 학생에게 빌려줄 필요가 없기 때문입니다.

이렇게 중복된 학생 번호를 제거함으로써, 이후의 빌려주기 과정에서 불필요한 비교를 피할 수 있습니다.

 

---

 

.copy()를 사용하는 이유는 집합에서 요소를 삭제할 때 발생할 수 있는 문제를 방지하기 위해서입니다.

Python에서 집합(set)을 순회하면서 요소를 삭제하면, RuntimeError가 발생할 수 있습니다. 이는 집합의 크기가 변경되면서 순회 중인 반복자가 혼란스러워지기 때문입니다.

예를 들어, 다음 코드는 에러를 발생시킵니다:

my_set = {1, 2, 3}
for x in my_set:
    if x == 2:
        my_set.remove(x)
이 코드는 RuntimeError: Set changed size during iteration라는 메시지를 출력합니다.

이를 해결하기 위해, 집합의 복사본을 순회하면서 원본 집합에서 요소를 삭제할 수 있습니다. .copy() 메서드는 집합의 복사본을 반환합니다. 따라서, 다음과 같이 수정할 수 있습니다:

my_set = {1, 2, 3}
for x in my_set.copy():
    if x == 2:
        my_set.remove(x)
이 코드는 안전하게 실행되며, my_set에서 요소 2를 제거합니다.

체육복 문제에서의 .copy()
체육복 문제에서도 마찬가지입니다. lost_set을 순회하면서 요소를 삭제할 때, .copy()를 사용하여 안전하게 요소를 제거할 수 있습니다.

for x in lost_set.copy():
    if x - 1 in reserve_set:
        lost_set.remove(x)
        reserve_set.remove(x - 1)
    elif x + 1 in reserve_set:
        lost_set.remove(x)
        reserve_set.remove(x + 1)
이 코드는 lost_set의 복사본을 순회하면서 원본 lost_set에서 요소를 삭제합니다. 이를 통해 RuntimeError를 피할 수 있습니다.

 

---

 

set의 .copy() 메서드는 얕은 복사를 수행합니다. 이는 set의 요소가 불변 객체인 경우에만 문제가 되지 않습니다.

set의 요소가 가변 객체라면, 얕은 복사로 인해 원본과 복사본이 같은 객체를 참조하게 됩니다. 따라서, 복사본에서 요소를 수정하면 원본에도 영향을 미칠 수 있습니다.

하지만, set의 요소는 일반적으로 불변 객체(예: 정수, 문자열 등)로 구성되므로, 얕은 복사가 문제를 일으킬 가능성은 낮습니다.

얕은 복사와 깊은 복사
얕은 복사: 객체의 참조를 복사하여, 원본과 복사본이 같은 객체를 참조합니다.

깊은 복사: 객체의 실제 값을 복사하여, 원본과 복사본이 서로 다른 객체를 참조합니다.

set의 경우, 얕은 복사가 충분하며, 깊은 복사를 별도로 제공하지 않습니다.