•
문제 설명 : 주어진 리스트 nums에서 서로 다른 세 개의 원소를 선택하여 만들 수 있는 “서로 다른 세 원소 조합”의 수를 계산
•
풀이 방법
◦
내 풀이는 리스트를 순회하면서, 공통 번호에 대한 정보를 얻은 후 조합을 사용하여 답을 구하였다.
◦
하지만 너무 시간 복잡도가 오래 걸려서, 다른 풀이를 찾아보았다.
•
시간복잡도 :
•
성공 코드
from itertools import combinations
class Solution:
def unequalTriplets(self, nums: List[int]) -> int:
group_count = []
last_index = 0
result = 0
for i, num in enumerate(nums):
if num != nums[last_index]:
group_count.append((nums[last_index], i - last_index))
last_index = i
# 마지막 번호 처리
group_count.append((nums[last_index], len(nums) - last_index))
if len(group_count) < 3:
return 0
for item in combinations(group_count, 3):
a, b, c = item
if a[0] != b[0] and b[0] != c[0] and a[0] != c[0]:
result += a[1] * b[1] * c[1]
return result
Python
복사
•
개선 코드(O(N))
“서로 다른 세 원소 조합” 이기 때문에, 각 숫자를 그룹화하여 갯수를 구한다.
이후 각 숫자가 중간에 존재할 경우, 몇개의 조합이 가능한지 구하는 방식이다.
이해가 좀 어려울 수 있다. 아래 예시를 참고하자
◦
EX) [1,2,3,2,2,4,4,5] → {1: 1, 2:3, 3:1, 4:2, 5:1} → [1,2,2,2,3,4,4,5] 와 같이 그룹화가 가능하다.
◦
각 숫자가 현재 중간에 있다고 가정하고, 좌/우 남은 요소의 갯수만큼 구하는 것이다.
◦
가장 처음, [1,2,2,2,3,4,4,5] 에서 1이 중간에 있을 경우이다.
▪
1은 가장 왼쪽이기 때문에, 왼쪽에 추가적인 숫자가 없고 오른쪽에 다른 숫자들 총 7개가 존재한다.
▪
그렇기 때문에, res 계산 시 res += left(0) * freq(1) * right(7)이 된다.
◦
이후 2~4까지는 좌우 숫자가 모두 존재하여 left와 right가 모두 양수이다.
◦
마지막으로 5는 가장 마지막 숫자로, 오른쪽에 다른 숫자가 없다. 하지만 왼쪽에 다른 숫자 총 7개가 존재한다.
▪
그렇기 때문에, res 계산 시 res += left(7) * freq(1) * right(0)이 된다.
from collections import Counter
from typing import List
class Solution:
def unequalTriplets(self, nums: List[int]) -> int:
# 각 숫자의 빈도수를 세기 위해 Counter 사용
c = Counter(nums)
res = 0
# 초기값 설정
left = 0
right = len(nums)
# 빈도수에 대해 반복
for _, freq in c.items():
# 현재 숫자의 빈도수만큼 right에서 빼기
right -= freq
# left * freq * right는 현재 숫자가 중간에 있을 때의 조합 수를 계산
res += left * freq * right
# left에 현재 숫자의 빈도수를 더하기
left += freq
return res
Python
복사