Count Triplets javascript로 풀기

/*

You are given an array and you need to find number of tripets 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.

 

당신에게 배열이 주어지고 당신은 3개의 인덱스를 찾아야 한다. (i,j,k)

그러한 각 인덱스의 요소들은 등비수열이고 공비가 r이며 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).

예를들어 arr = [1,4,16,64]이면. r이 4이고, 우리는 1,4,16 4,16,64를 얻고 각 인덱스는 0,1,2 1,2,3 이다.

 

Complete the countTriplets function in the editor below. 

아래 편집기에서 countTriplets를 완성하라

 

It should return the number of triplets forming a geometric progression for a given r as an integer.

r에 대해 등비수열을 형성하는 3개의 숫자의 갯수를 구하라

 

countTriplets has the following parameter(s):

arr: an array of integers

r: an integer, the common ratio

countTriplets에 파라미터는 아래와 같다.

arr : 정수형 배열

r : 정수, 공비

 

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

첫번째 줄에는 2개의 공백으로 n과 r이 주어진다. 배열의 크기와 공비이다.

The next line contains n space-seperated integers arr[i].

다음줄에는 n개의 공백으로 정수 배열 arr가 주어진다.

 

-- 풀이 --

2가지가 떠오른다.

1. 3개의 인덱스를 구하는 모든 경우의 수를 구한다음 하나씩 순회하면서 등비수열인지 체크하는것

일단 안될것같다 기각

 

2. 

2.1 arr[0]~arr[arr.length-1]을 각각 dictionary에 넣는다.

    5 5

    1 5 5 25 125 인 배열이면

 

    1 = 1

    5 = 2

    25 = 1

    125 = 1

 

    6 3

    1 3 9 9 27 81 이면

 

    1 = 1

    3 = 1

    9 = 3

    27 = 1

    81 = 1

 

2.2 arr[0]~arr[arr.length-1]의 등비수열을 구한다.

    1 5 25 125 625

    1 3 9 27 81 243

2.2 등비수열을 순회하면서 1 이상인 값이 있을때 해당 값부터 등비수열에 해당하는 값이 있는지 체크한다.

1 3 9 27 81 243 인 경우

 

1 = 1이므로

1 3 9가 있는지 체크

1 1 2개 있다.

그러면 등비수열의 갯수도 2개다.

만약 

1 1 3개 있다면 등비수열의 갯수도 3개다.

1 3 9 

    9(2)

    9(3) 가 가능하니까

1 2 2 개 있다면 등비수열의 갯수는 

1 3(1) 9(1)

1 3(2) 9(1)

1 3(1) 9(2)

1 3(2) 9(2) 개 이므로 4개다.

 

2 2 2개 있다면

11 31 91

11 31 92

11 32 91

11 32 92

 

12 31 91

12 31 92

12 32 91

12 32 92

 

8개다.

 

즉 i*j*k개다.

 

등비수열이 1 3 9 27 81 일 경우

1 3 9

3 9 27

9 27 81

이런식으로 돌리자

 

--> 완벽했다고 생각했는데

1 1 1 1 1 1 1 1 ... 100개

했을때 문제가 생기며, 그 외에도 틀린답이 다수 존재하며 일부는 타임아웃도 걸린다.

로직 자체를 바꿔서 떠올려야 할듯

 

--> 검색 찬스로 대충 보니 해쉬를 2개로 나누랜다.

처음에는 무슨소리인지 이해가 안되었는데 잘 생각해보니

무조건 돌면서

i<j<k가 있는지 체크하면 되는것이다.

 

arr은 그냥 순회하면서 arr*r만 해준다.

 

공비가 3이고

1 3 9 27 81이면

 

1*3 3*3 9*3 27*3 81*3 이 있는지 보는것이다.

 

첫번째 값인 i는 의미없고 두번째 값인 j와 3번째 값인 k가 있을때 count+1을 한다.

만약 2번째 값이 2개라면 3번째 값도 2개가 되겠지

이런식으로 반복하면 결과값이 나온다.

 

구글의 도움이 없었다면 풀지 못했을 것.

 

*/

 

var arr = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1];

var r = 1;

// var arr=[1,2,2,4];

// var r = 2;

var dic1 = {};

var dic2 = {};

var total = 0;

for(var i=0;i<arr.length;i++){

    var val = arr[i];

    if(dic2[val]){

        total +=dic2[val];

    }

    if(dic1[val]){

        if(dic2[val*r])

            dic2[val*r] += dic1[val];

        else

            dic2[val*r] = dic1[val];

    }

    if(dic1[val*r])

        dic1[val*r]+=1;

    else

        dic1[val*r]=1;

}

console.log(total);