You are given an array and you need to find number of tripets of indices such that the elements at those indices are in geometric progression for a given common ratio and .
For example, . If , we have and at indices and .
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):
Input Format
The first line contains two space-separated integers and , the size of and the common ratio. The next line contains space-seperated integers .
Constraints
Output Format
Return the count of triplets that form a geometric progression.
Sample Input 0
4 2
1 2 2 4
Sample Output 0
2
Explanation 0
There are 2 triplets in satisfying our criteria, whose indices are (0, 1, 3) and (0, 2, 3)
Sample Input 1
6 3
1 3 9 9 27 81
Sample Output 1
6
Explanation 1
The triplets satisfying are index (0, 1, 2), (0, 1, 3) , (1, 2, 4), (1, 3 ,4), (2, 4, 5) and (3 , 4, 5)
Sample Input 2
5 5
1 5 5 25 125
Sample Output 2
4
Explanation 2
The triplets satisfying are index (0, 1, 3), (0, 2, 3), (1, 3, 4), (2, 3, 4) .
주어진 수열에서 주어진 값 r의 순차 배수를 세개 찾는 문제이다. map left, right두 개를 활용하여 초기에 수열을 for루프를 돌면서 right map에 수열의 각 숫자의 갯수를 넣어준다.
그리고 다시 수열을 for loop를 돌면서 right map에 해당 숫자의 갯수를 한개 줄여주고, 현재 숫자가 r값으로 나누어 떨어지면 배수 이므로 answer 값에 (현재숫자/r의 갯수)x(현재숫자x의 갯수) 를 누적하여 더한다.
사용한 숫자는 left map에 해당 숫자의 갯수를 한개 증가시켜서 위에서 answer값을 계산할때 사용하게 한다.
right map에서 현재 숫자 1개를 줄여서 현재숫자 1개의 사용함으로 현재숫자의 갯수는 1이어서 answer에 곱하지 않는다. triplet 세개로 구성됨으로 현재의 숫자에서 r로 나눈 숫자의 갯수가 triplet의 첫번째 원소 갯수 이며, r을 곱한 숫자가 triplet의 마지막 숫자가 된다. 그래서 현재숫자를 1개 사용 했을때 (현재숫자/r의 갯수)x(현재숫자x의 갯수) 가 현재 숫자 1개로 구성할 수있는 triplet의 갯수가 된다.
잘 생각이 안나서 hackerrank 답 참조함…
#include <bits/stdc++.h>
using namespace std;
string ltrim(const string &);
string rtrim(const string &);
vector<string> split(const string &);
// Complete the countTriplets function below.
long countTriplets(vector<long> arr, long r) {
map<long long, long long> left,right;
long answer = 0;
for(int i = 0; i< arr.size(); i++){
right[arr[i]]++;
}
for(int i = 0; i < arr.size(); i++) {
right[arr[i]]--;
if(arr[i]% r == 0) {
answer += left[arr[i]/r]*right[arr[i]*r];
}
left[arr[i]]++;
}
return answer;
}
int main()
{
ofstream fout(getenv("OUTPUT_PATH"));
string nr_temp;
getline(cin, nr_temp);
vector<string> nr = split(rtrim(nr_temp));
int n = stoi(nr[0]);
long r = stol(nr[1]);
string arr_temp_temp;
getline(cin, arr_temp_temp);
vector<string> arr_temp = split(rtrim(arr_temp_temp));
vector<long> arr(n);
for (int i = 0; i < n; i++) {
long arr_item = stol(arr_temp[i]);
arr[i] = arr_item;
}
long ans = countTriplets(arr, r);
fout << ans << "\n";
fout.close();
return 0;
}
string ltrim(const string &str) {
string s(str);
s.erase(
s.begin(),
find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
);
return s;
}
string rtrim(const string &str) {
string s(str);
s.erase(
find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(),
s.end()
);
return s;
}
vector<string> split(const string &str) {
vector<string> tokens;
string::size_type start = 0;
string::size_type end = 0;
while ((end = str.find(" ", start)) != string::npos) {
tokens.push_back(str.substr(start, end - start));
start = end + 1;
}
tokens.push_back(str.substr(start));
return tokens;
}