-
Sales by Match알고리즘 풀이/HackerRank 2021. 12. 5. 08:52728x90
문제 이해 및 분석
1. pair 로 이루어 질 수 있는 n개의 수가 존재한다.
2. pair는 두개씩
3. 주어진 n개의 수에서 각 숫자가 이루는 pair 의 총 합을 구한다.
문제 풀이
1. 주어진 값을 정렬한다.
2. 그리고 중복을 제거한다. 그러면 고유한 값만 남게된다.
3. 정렬된 원본 값에서 고유한 값이 몇개 존재하는지 카운트 하고 pair는 두개씩이므로 2로 나누고 몫을 더한다.
int sockMerchant(int n, vector<int> ar) { int pairOfSums = 0; sort(ar.begin(), ar.end()); vector<int> sortedRaw(ar.size()); copy(ar.begin(), ar.end(), sortedRaw.begin()); ar.erase(unique(ar.begin(), ar.end()), ar.end()); for (auto i : ar) { pairOfSums += count(sortedRaw.begin(), sortedRaw.end(), i) / 2; } return pairOfSums; }
생각해 볼 점
1. 카피해서 풀었는데 통과했다.
2. 카피하는게 마음에 들지 않는다.
3. 카운트 하는것도 다시 선형으로 돌아야 하므로 마음에 들지 않는다.
728x90'알고리즘 풀이 > HackerRank' 카테고리의 다른 글
New Year Chaos (0) 2021.12.05 Repeated String (0) 2021.12.05 Interview Preparation Kit (0) 2021.12.05 Jumping on the Clouds (0) 2021.12.05