해당 문제는 정수 배열 numbers가 주어지면
그 배열에서 서로 다른 인덱스의 두 수를 뽑아 더해서 만들 수 있는 모든 수를 오름차순으로 배열에 담아 return하는 함수를 만드는 것이었다.
처음 짠 코드는 다음과 같다.
def solution(numbers):
length=len(numbers)
return list(set([numbers[i]+numbers[k] for i in range(length-1) for k in range(i+1,length)]))그런데 딱 두 개의 케이스가 통과하지 못하고 있었다.
아래는 혹시나 하는 마음에 sorted를 넣어준 코드.
def solution(numbers):
length=len(numbers)
return sorted(list(set([numbers[i]+numbers[k] for i in range(length-1) for k in range(i+1,length)])))잘 된다.
나는 set이 자동으로 안의 요소들을 sort하는 것이라고 생각했다.
그렇게 착각할 만 했던 것이, 실제로 테스크 케이스에서 set이 sort를 진행하는 것처럼 작동했기 때문이다.
이유가 궁금했다.
혹시나 하는 마음에 질문하기 칸에 나와 같은 고민을 한 사람이 있는지 찾아봤는데.... 있었다!
안녕하세요.
set을 사용한다고 해서 자동으로 오름차순으로 정렬되지 않습니다. Python의 set은 BBST가 아니라 HashSet의 형태를 하고 있기 때문입니다.import random print(list(set(random.choices(range(1000), k=20))))이 코드를 실행해보시기 바랍니다.
감사합니다.
약간의 구글링 결과
BBST는 Balanced binary search tree의 약자며, HashSet과 BBST는 자료 구조를 의미하는 듯 하다.
BBST의 경우는 아래 사이트를 확인해보자.
https://jackpot53.tistory.com/17
https://ko.wikipedia.org/wiki/이진_트리
간략하게 말하자면 이진 트리의 균형을 맞춰서 비용을 감소시키는 방식으로 보인다.
HashSet은 '중복만'을 체크하는 자료구조로 보인다.
그러나 HashSet이 '중복만' 체크한다면 몇 가지 테스트에서 오름차순으로 정렬되어서 나온 경우를 설명하지 못한다.
https://stackoverflow.com/questions/23140189/how-does-hashset-sort
이 링크는 언어는 다르지만 약간의 힌트를 엿볼 수 있었다. 그것은 HashSet이 sorting mechanism을 갖고 있다는 것이다. 그러나 이것이 꼭 결과가 정렬되어 나올 것이라는 것을 보장하지는 않는 것 같다.
