HackerRank - Count Triplets

https://www.hackerrank.com/challenges/count-triplets-1/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dictionaries-hashmaps

Count Triplets | HackerRank

간단해 보이지만 어김없이 시간 제약에 걸리는 문제입니다.

 

문제 : 숫자 리스트 arr과 공비 r이 주어졌을 때,

arr[i] = 임의의 숫자 k

arr[j] = k * r

arr[k] = k * r * r

를 만족하는 (i,j,k)의 총 갯수를 구하는 문제입니다. 이 때 i < j < k를 만족해야 합니다.

 

예를 들어,

 

arr = [1, 2, 2, 4] , r = 2라고 할 때

arr[0] = 1, arr[1] = 2, arr[3] = 4 (i = 0, j = 1, k = 3)

arr[0] = 1, arr[2] = 2, arr[3] = 4 (i = 0, j = 2, k = 3)

 

라는 두개의 해를 찾을 수 있습니다. 

 

방법 : 저는 찾아야 하는 3개의 숫자 중 가운데 숫자(arr[j])를 기준으로 i,j,k의 조합을 찾아내기로 했습니다.

* arr[j]의 특성은 r로 나눴을 때 나머지가 0이라는 점입니다.(arr[k]도 마찬가지긴 합니다.)

 

1) Counter 라이브러리를 활용하여 arr의 구성 요소에 대한 dict를 생성한다.

2) 빈 라이브러리 dict2를 생성한다.

3) 리스트에 대해 for loop을 돌리면서 나오는 숫자(num)가 r로 나눴을 때 나머지가 0인지 확인한다.

  3.1) 나머지가 0이 아닌 경우 : dict2[num]에 1을 더하고, dict[num]에 1을 빼준다.

  3.2) 나머지가 0인 경우 :

          1) dict2[num//r]이 존재하고, dict[num*r]이 존재할 경우, 정답에 dict2[num//r] * dict[num*r]을 더한다.

          2) 위의 둘 중 하나가 없는 경우 dict2[num]에 1을 더하고, dict[num]에 1을 빼준다.

 

위의 작업을 리스트의 처음부터 끝까지 반복하면 정답을 구할 수 있습니다 -!