문제 12: 목표 합을 가진 쌍 찾기

Source: Dev.to

문제 설명

목표 합계가 되는 리스트 내 모든 고유한 숫자 쌍을 찾는 함수를 작성하세요.
함수는 각 쌍을 정렬된 형태의 튜플로 담은 리스트를 반환해야 합니다. 각 쌍은 한 번만 나타나야 합니다.

예시

find_pairs([1, 5, 7, -1, 5], 6)   # → [(1, 5), (-1, 7)]
find_pairs([2, 3, 4, 5], 9)      # → [(4, 5)]

풀이

Python 구현

def find_pairs(lst, target):
    """
    Finds all unique pairs in the list that sum up to the target.
    Returns a list of tuples sorted within each pair.
    """
    seen = set()
    pairs_found = set()
    for num in lst:
        complement = target - num
        if complement in seen:
            pairs_found.add((min(num, complement), max(num, complement)))
        seen.add(num)
    return list(pairs_found)

# Test cases
print(find_pairs([1, 5, 7, -1, 5], 6))   # Output: [(1, 5), (-1, 7)]
print(find_pairs([2, 3, 4, 5], 9))      # Output: [(4, 5)]

설명

1. 보여진 숫자 추적 – seen은 이미 처리한 숫자를 저장하는 집합으로, O(1) 조회가 가능합니다.
2. 쌍 저장 – pairs_found는 튜플의 집합입니다. 집합을 사용하면 중복된 쌍이 자동으로 무시됩니다.
3. 리스트 순회
   • 각 num에 대해 보완값 target - num을 계산합니다.
   • 보완값이 seen에 이미 존재하면 유효한 쌍이 발견된 것입니다.
   • min과 max를 사용해 튜플을 정렬된 형태로 pairs_found에 추가합니다.
4. seen 업데이트 – 보완값을 확인한 후 현재 num을 seen에 추가하여 이후 요소들의 보완값이 될 수 있게 합니다.
5. 결과 반환 – 집합에 저장된 쌍을 리스트로 변환하여 반환합니다. 리스트 내 쌍의 순서는 보장되지 않지만, 각 쌍은 고유하고 정렬된 상태입니다.