snoopybox

Problem :

https://www.hackerrank.com/challenges/beautiful-triplets/problem

My Solution :

#!/usr/bin/env python3


def beautiful_triplets(d, arr):
    arr_set = set(arr)
    count = 0
    for a in arr:
        if a+d in arr_set and a+2*d in arr_set:
            count += 1
    return count


n, d = map(int, input().split())
arr = list(map(int, input().rstrip().split()))
result = beautiful_triplets(d, arr)
print(result)

Comment :

위 풀이는 이 문제를 처음 읽었을 때 바로 떠올렸던 풀이이고 (set을 활용한 in 연산의 효율화)

아래 풀이는 counting을 해서 갯수 곱으로 계산해보겠다는 아이디어가 떠올라 시도해본 것이다.

My Solution2 :

#!/usr/bin/env python3


def beautiful_triplets(d, arr):
    counter = {}
    count = 0
    for a in arr:
        counter.setdefault(a, 0)
        counter[a] += 1
    for a in counter:
        count += counter[a] * counter.get(a+d, 0) * counter.get(a+2*d, 0)
    return count


n, d = map(int, input().split())
arr = list(map(int, input().rstrip().split()))
result = beautiful_triplets(d, arr)
print(result)

Comment :

이번에는 counter를 dictionary 대신 list로 바꿔보았다.

My Solution3 :

#!/usr/bin/env python3


def beautiful_triplets(d, arr):
    counter = [0]*(10**5)
    count = 0
    for a in arr:
        counter[a] += 1
    for a in set(arr):
        count += counter[a] * counter[a+d] * counter[a+2*d]
    return count


n, d = map(int, input().split())
arr = list(map(int, input().rstrip().split()))
result = beautiful_triplets(d, arr)
print(result)