[Codewars]5kyu - Sum of pairs

어떤 수들의 리스트가 주어지고, target이 주어지는데, list에서 target을 맞추기 위한 쌍을 찾아서 return하면 된다.

 

쉬워 보이는데 막상 하면 어렵다. 그냥 이중 for문을 사용하면 무조건 시간 초과가 뜬다. NOTE에 쓰여 있듯이 길이가 천만이 넘는 리스트도 나오기 때문이다.

 

그리고 문제의 설명이 좀 모호한 점이 있는데, 해당 target을 만들기 위한 쌍이 여러개 있다면 두 수의 인덱스 중 나중 인덱스가 가장 빠른(왼쪽에 있는) 쌍을 골라 내보내야 한다.

 

이중 for문을 사용한다면 시간 복잡도는 O(n^2)이고 그 코드는 이렇다.

 

def sum_pairs(ints, s):
    for i in range(1,len(ints)):
        for j in range(i):
            if ints[i] + ints[j] == s:
                return [ints[j],ints[i]]

 

그러나 이는 얄짤없이 시간 초과를 맞는다.

 

너무 많은 검사를 하기에 시간 초과를 맞는다. 그리고 중복되는 수도 많기 때문에, 이런 식으로 작성하면 낭비가 심하다.

 

가장 많은 clever를 받은 답안이다.

def sum_pairs(lst, s):
    cache = set()
    for i in lst:
        if s - i in cache:
            return [s - i, i]
        cache.add(i)

 

cache 집합을 만든 뒤, target에서 list의 i값을 빼 보고, cache에 저장되어 있지 않다면 cache에 i를 저장하는 방식을 이용했다. 이렇게 하면 중복되는 수는 다시 검사하지 않을 뿐더러, list를 한번만 탐색하기 때문에 평균 시간 복잡도는 O(n)이다!