강의로 돌아가기
niceinno

set을 이용한 풀이를 진행하실 때 set을 정렬 해야하는 이유는 무엇인가요?

l 에는 체육복을 잃어버려서 없는 학생들이 있고 r 에는 여벌의 체육복을 가진 학생들이 있는데
각각의 r 집합에 있는 학생들에 대하여 앞, 뒤로 학생을 확인하여 줄 수 있는 학생이 있다면 l 집합에서 그 학생을 제외시키는
알고리즘을 작성하셨는데, for문을 도는 과정에서 r을 sorting 시키는 이유가 궁금합니다.

set에는 순서가 없이 자료들이 저장되고,
만일 set에 5 7 8 2 4 이런식으로 정렬되지 않은 상태로 for문에 하나씩 대입된다고 해도 앞뒤를 살피는 알고리즘에는
지장이 없을 것 같다는 생각이 들었고 작성해주신 알고리즘에서도 for문의 sorted를 삭제해봐도 테스트는 통과하여
이상이 없어 보이는데 제가 놓치는 부분이 있을까요?

작성중인 코드―solution.py
1
2
3
4
5
6
7
8
9
10
def solution(n, lost, reserve):
    s = set(lost) & set(reserve)
    l = set(lost) - s
    r = set(reserve) - s
    for x in r:
        if x-1 in l:
            l.remove(x-1)
        elif x+1 in l:
            l.remove(x+1)
    return n - len(l)
2 개의 답변
이시윤

이에 대해서는, 동영상 강의의 06:07 부터 내용을 참고하십시오. 특히, 07:21-07:53 의 내용이 이와 직접 연관된 사항을 언급하고 있습니다.

짧게 말하면, 정렬되지 않은 상태로 (무작위 순서로) r 에 들어 있는 번호들을 고려하고 각 번호에 대해서 앞 번호 (코드에서 x - 1) 와 뒷 번호 (x + 1) 의 학생이 l 에 들어 있는지를 검사하게 되면, 체육복을 빌려줄 수 있는 학생이 남는데도 빌려주는 것을 결정하는 순서가 꼬여서 빌려줄 수 없는 상황 (동영상 강의 예시를 참고) 이 발생할 수 있습니다.

테스트를 모두 통과하는 것은, 이 문제의 테스트 케이스 중 위에 말한 바와 같은 경우가 발생하도록 만들어진 경우가 없기 때문입니다. Python set 에 의하여 원소들이 검사되는 (코드에서 L5) 순서는 정해져 있지 않기 때문에, 이런 경우가 반드시 발생하도록 테스트 케이스를 만드는 것은 보장할 수 없는 일이기도 합니다.

niceinno

답변 감사드립니다!

답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.