물론 정답 배열의 개수가 순차적으로 증가하기 때문에 정확하게는 O(n2) 알고리즘이 아니지만, 그에 준하는 알고리즘이라는 상황은 변하지 않습니다. 이 부분을 개선해야 합니다. 그러나 중복된 숫자를 체크하는 부분은 함부로 빼거나 대체할 수 없습니다. 이럴 경우 구성을 고치는 것보다는 검색 비용을 줄이는 것이 좋습니다. 딕셔너리({})를 사용해서 말이죠.
1. answer 변수를 배열이 아니라 객체(object, 여기에서는 딕셔너리(dict))로 변경합니다.
2장에서 언급했듯이 딕셔너리에서 해당 값이 있는지 검색하는 비용은 O(1)로 가장 빠릅니다. 이 점을 이용하여 정답 변수를 딕셔너리로 초기화한 다음, 키를 집합의 숫자로 지정하면(값은 아무거나 사용해도 됩니다) 중복 검사 시간은 O(n)이 아니라 O(1)이면 충분합니다.
answer = {}
2. 문자열을 적절한 방법으로 쪼개고, 결괏값의 길이로 정렬합니다.
앞의 코드와 동일한 방식으로 구현하되 과정을 한 번에 합쳐서 진행하겠습니다.
s = sorted(s[2:-2].split("},{"), key=len)