[해커랭크] Count Triplets (C++)

문제 링크: 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

1. 주의할 점

- R이 1이라면?

- 범위는 Long이다. 개수 또한 Long이 될 수 있다

- 배열의 값이 내림차순으로 정리되는 경우, 답은 0이다

 

[생각한 TC]

#1
5 2
1 2 4 2 4

#2
4 3
16 4 1

#3
10 1
5 5 5 5 5 5 5 5 5 5

#4
4 3
2 5 8 11

 

2. 구현

- O(N*lgN)의 시간복잡도를 가진다

- Map배열 m[2]를 사용하여 계산한다. A = Arr[i], B = Arr[j], C = Arr[k]라고 가정한다.(A*R*R = B*R = C가 성립)

- A에 대한 정보는 m[0]에, B에 대한 정보는 m[1]에 저장한다. 

- 모든 Arr배열 Val에 대해 Val, Val/R, Val/(R*R) 나눈 값에 대한 처리를 한다. 현재 비교하는 값인 Val은 A, B, C 모두가 될 수 있는 가능성이 있기 때문

- Val이 C인 경우 -> Val/R 값인 B가 m[1]에 존재해야 하고, Val/(R*R)값인 A가 m[0]에 존재해야 한다. 존재한다면, B가 나타난 횟수만큼 더한다

- Val이 B인 경우 -> Val/R값인 A가 m[0]에 존재해야 한다. 존재한다면, m[1][Val]에는 m[0][Val/R] 즉, m[0][A]만큼 더한다

- Val이 A인 경우 -> m[0]에 추가한다

map<long, long> m[2];
// Complete the countTriplets function below.
long countTriplets(vector<long> arr, long r) {
    long result = 0;
    for(int i=0;i<arr.size();i++){
        int val = arr[i];
        // /(r*r)
        if(val%(r*r)==0 && m[1].find(val/r)!=m[1].end() && m[0].find(val/(r*r))!=m[0].end())
            result +=m[1][val/r];
        
        // /r
        if(val%r==0 && m[0].find(val/r)!=m[0].end()){           
            m[1][val] += m[0][val/r];
        }       
        //기본
        if(m[0].find(val)!=m[0].end())
            m[0][val]++;
        else 
            m[0][val]=1;
    }
    
    return result;
}