파이썬으로 '좋은 쌍(Good Pair)'의 개수 구하는 프로그램

문제 설명

배열 nums가 주어졌을 때, nums[i]와 nums[j]의 값이 같으면서 i < j를 만족하는 인덱스 쌍 (i, j)를 '좋은 쌍(good pair)'이라고 정의합니다. 우리가 구해야 할 것은 이러한 좋은 쌍의 총 개수입니다.

예를 들어 입력이 nums = [5,6,7,5,5,7]이라면, 조건을 만족하는 쌍은 인덱스 기준으로 (0, 3), (0, 4), (3, 4), (2, 5)로 총 4개이므로 출력 결과는 4가 됩니다.

해결 접근 방법

가장 직관적인 방법은 모든 가능한 인덱스 쌍을 확인하는 브루트포스(완전 탐색) 방식입니다.

• 카운트 변수 count를 0으로 초기화합니다.
• 배열의 크기를 n에 저장합니다.
• 첫 번째 반복문으로 i를 0부터 n-1까지 순회합니다.
• 두 번째 반복문으로 j를 i+1부터 n-1까지 순회합니다.
• nums[i]와 nums[j]가 같다면 count를 1 증가시킵니다.
• 모든 탐색이 끝나면 count를 반환합니다.

예제 코드 (Python)

아래 구현을 통해 동작 과정을 더 잘 이해할 수 있습니다.

def solve(nums):
    count = 0
    n = len(nums)
    for i in range(n):
        for j in range(i+1, n):
            if nums[i] == nums[j]:
                count += 1
    return count

nums = [5,6,7,5,5,7]
print(solve(nums))

입력

[5,6,7,5,5,7]

출력

4

더 효율적인 방법: 해시맵(Counter) 활용

위 완전 탐색 방법의 시간 복잡도는 O(n²)입니다. 배열의 크기가 커지면 비효율적이므로, collections.Counter를 이용하면 시간 복잡도를 O(n)으로 줄일 수 있습니다.

핵심 아이디어는 다음과 같습니다. 어떤 값이 f번 등장했다면, 그 값으로 만들 수 있는 좋은 쌍의 수는 조합 공식에 따라 f × (f − 1) / 2입니다.

from collections import Counter

def solve(nums):
    freq = Counter(nums)
    return sum(f * (f - 1) // 2 for f in freq.values())

nums = [5,6,7,5,5,7]
print(solve(nums))  # 출력: 4

두 방법 모두 같은 결과를 반환하지만, 입력 크기가 큰 경우에는 해시맵을 활용한 최적화 풀이가 훨씬 빠르게 동작합니다.