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

불러오는 중입니다...

 

원문 : 

You are given an array and you need to find number of Triplets of indices (i, j, k)  such that the elements at those indices are in geometric progression for a given common ratio r and i < j < k

For example, arr = [ 1, 4, 16, 64 ]. If r = 4, we have [1, 4, 16] and [4, 16, 64]  at indices (0, 1, 2) and ( 1, 2, 3 ).

 

Function Description

Complete the countTriplets function in the editor below. It should return the number of triplets forming a geometric progression for a given  as an integer.

countTriplets has the following parameter(s):

• arr: an array of integers
• r: an integer, the common ratio

Input Format

The first line contains two space-separated integers n and r, the size of arr and the common ratio.
The next line contains n space-seperated integers arr[i] 

 

Output Format

Return the count of triplets that form a geometric progression.

 

 

Explanation 0

There are 2 triplets in satisfying our criteria, whose indices are (0,1,2) and (0,2,3)

 

 

번역:

당신은 주어진 배열에서 세개의 인덱스 ( i, j, k) 를 찾아야 한다. 그 인덱스의 요소들은 등비수열이며 공비는 r 이며 i < j < k 이다. 

예를 들어 arr = [ 1, 4, 16, 64 ] 일때 만약 r = 4 라면,  우리는 [1, 4, 16] 와 [4, 16, 64] 의 인덱스인  (0, 1, 2) 와 ( 1, 2, 3 )을 갖게 된다. 

 

기능 설명

아래의 에디터에서 countTriplets 를 완성 하세요. 주어진 integer 형태에서 등비수열형태의 세개를 리턴하여야 합니다. 

countTriplets은 다음과 같은 변수를 갖고있습니다. 

arr : integers의 배열 

r : integer, 공비

 

입력 형태

첫번째 라인은 공백으로 구분된 두개의 integer는 arr의 사이즈와 공비인 n, r 이 포함되어있습니다. 

다음 라인은 n 이며 공백으로 구분된 integer arr[i] 이 들어있습니다. 

 

출력 형태 

세개의 등비수열 형태의 갯수를 리턴하세요. 

 

설명 0 

(0,1,2) 와 (0,2,3)의 인덱스인 두개의 세짝을 만족합니다. 

 

정답 코드 : 

https://github.com/lorh2700/algo/tree/master/bjtest/src/HakerRank/CountTriplets

lorh2700/algo

 

팁 :

1. 첫번째 값 찾고 두번쨰 값 찾고 세번째 값 찾는 방법으로는 시간초과가 걸릴 것입니다.

2. for문 한번에 끝내야 성공 할 수 있습니다. 

3. 저의 경우는 for문 한개와 해쉬맵 두개로 풀었습니다. 

3-1 3개의 고정 짝수라는 제약이 있기때문에 중간값과 끝의값을 저장

4. midium 맞아?