파이썬으로 nums[i] = nums[j]를 만족하는 쌍(i, j)의 개수 구하기

문제 개요

배열 nums가 주어졌을 때, nums[i]와 nums[j]의 값이 서로 같으면서 인덱스 i와 j는 서로 다른 쌍(i, j)의 개수를 구하는 문제입니다.

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

해결 접근 방법

이 문제는 각 값이 배열에 몇 번 등장하는지 먼저 세어 놓으면 효율적으로 해결할 수 있습니다. 순서는 다음과 같습니다.

1. 등장 횟수를 저장할 빈 딕셔너리(맵) d를 생성합니다.
2. nums의 각 원소 c에 대해 d[c]의 개수를 하나씩 증가시킵니다.
3. 결과값 res를 0으로 초기화합니다.
4. d에서 등장 횟수가 1보다 큰 각 원소 c에 대해 res += d[c] * (d[c] - 1)을 수행합니다.
5. 최종적으로 res를 반환합니다.

동작 원리

어떤 값이 배열에 n번 등장한다면, 그 값들 중에서 서로 다른 두 인덱스를 뽑아 만들 수 있는 순서쌍의 개수는 n × (n-1)개입니다. 예를 들어 값 1이 인덱스 0과 2에 있다면 (0, 2)와 (2, 0) 두 쌍이 만들어집니다. 따라서 각 값의 등장 횟수에 이 공식을 적용해 모두 더하면 정답을 얻을 수 있습니다.

구현 예제

def solve(nums):
    d = {}
    for c in nums:
        d[c] = d[c] + 1 if c in d.keys() else 1

    res = 0
    for c in (x for x in d if d[x] > 1):
        res += (d[c] * (d[c]-1))

    return res

nums = [1,3,1,3,5]
print(solve(nums))

입력

[1,3,1,3,5]

출력

4

복잡도 분석

배열을 한 번만 순회하며 빈도를 세므로 시간 복잡도는 O(n)이고, 각 고유 값의 개수만큼 저장 공간이 필요하므로 공간 복잡도 역시 O(n)입니다. 이중 반복문으로 모든 쌍을 직접 비교하는 O(n²) 방식보다 훨씬 효율적입니다.