파이썬으로 배열에서 같은 값을 가지는 인덱스 쌍 개수 구하는 프로그램

문제 개요

숫자로 이루어진 리스트 nums가 주어졌을 때, nums[i]와 nums[j]의 값이 서로 같으면서 i < j를 만족하는 인덱스 쌍의 개수를 구하는 문제입니다.

예를 들어 입력이 nums = [5, 4, 5, 4, 4]라면 출력은 4가 됩니다. 조건을 만족하는 인덱스 쌍이 (0, 2), (1, 3), (1, 4), (3, 4)로 총 네 개이기 때문입니다.

해결 접근 방법

모든 인덱스 쌍을 하나씩 비교하는 브루트 포스 방식은 O(n²)의 시간 복잡도를 가지므로, 데이터 크기가 커지면 비효율적입니다. 대신 다음 단계를 따르면 O(n) 시간에 문제를 해결할 수 있습니다.

• 각 숫자의 등장 빈도를 딕셔너리 형태로 계산합니다. 파이썬의 Counter를 활용하면 편리합니다.

• 결과를 저장할 변수 count를 0으로 초기화합니다.

• 빈도 값 n마다 n * (n - 1) // 2를 더합니다.

• 최종 count를 반환합니다.

왜 n × (n − 1) / 2일까?

같은 값이 n번 등장한다면, 이들 중 두 개를 선택하는 경우의 수는 조합 공식 C(n, 2) = n × (n − 1) / 2와 같습니다. 예를 들어 숫자 4가 세 번 등장하면 가능한 쌍은 3 × 2 / 2 = 3개입니다.

구현 예제

다음 코드를 통해 직접 확인해 보세요.

from collections import Counter

def solve(nums):
   c = Counter(nums)
   count = 0
   for n in c.values():
      count += n * (n - 1) // 2
   return count

nums = [5, 4, 5, 4, 4]
print(solve(nums))

입력

[5, 4, 5, 4, 4]

출력

4

정리

이 방법은 리스트를 한 번만 순회하며 빈도를 집계하고, 각 빈도에 대해 상수 시간 연산만 수행하므로 전체 시간 복잡도는 O(n)입니다. 공간 복잡도 역시 고유한 값의 개수에 비례하여 최대 O(n)입니다. 중복 쌍을 찾는 유사한 문제(예: 좋은 쌍(Good Pairs) 문제)에도 동일하게 적용할 수 있는 실용적인 패턴입니다.