Count Triplets | HackerRank
Return the count of triplets that form a geometric progression.
www.hackerrank.com
간단해 보이지만 어김없이 시간 제약에 걸리는 문제입니다.
문제 : 숫자 리스트 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을 빼준다.
위의 작업을 리스트의 처음부터 끝까지 반복하면 정답을 구할 수 있습니다 -!
'Computer Science > 알고리즘' 카테고리의 다른 글
백준 - 괄호(9012) (1) | 2020.12.20 |
---|---|
HackerRank - Frequency Queries (0) | 2020.04.02 |
HackerRank - Array Manipulation (0) | 2020.03.31 |
Hackerrank - Minimum Swaps2 (0) | 2020.03.31 |
Hackerrank - New Year Chaos (0) | 2020.03.16 |