[프로그래머스 Level 2] 시소 짝꿍(C++)

코딩테스트 연습 - 시소 짝꿍 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

100, 100, 200이 있을 때 {100,200}으로 한 개만 있는 것이 아니라, 각각 구별해야한다. 따라서 {100-1,200}, {100-2,200}로 2개이다.  weigth 값의 범위는 100~1,000인데 배열의 총 길이는 100,000이다. 따라서 중복된 것을 제외하면 배열의 총 길이는 901이다. 따라서 중복되는 것의 개수를 구한 arr 배열을 따로 마련한 다음 중복된 것이 없는 배열을 2차원 for문 탐색으로 돌리면서 균형을 이루는 경우가 있으면 arr배열에서 개수를 가져와 서로 곱해주고 이를 answer에 더해주면 된다.

이전에 중복되는 것끼리 짝을 지어줘야하는데 이는 중복된것개수C2 해주면 된다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int arr[1001];
long long store[100001];

long long solution(vector<int> weights) {
	store[2] = 1;
	store[3] = 3;
	long long sum = 3;
	for (int i = 4; i <= 100000; i++) {
		store[i] = store[i - 1] + sum;
		sum++;
	}
	long long answer = 0;
	for (int i = 0; i < weights.size(); i++) {
		arr[weights[i]]++;
	}
	for (int i = 100; i <= 1000; i++) {
		answer += store[arr[i]];
	}
	sort(weights.begin(), weights.end());
	weights.erase(unique(weights.begin(), weights.end()), weights.end());
	for (int i = 0; i < weights.size(); i++) {
		for (int j = i + 1; j < weights.size(); j++) {
			if (((weights[i] * 3) == (weights[j] * 2)) || ((weights[i] * 4) == (weights[j] * 2)) || ((weights[i] * 4) == (weights[j] * 3))) {
				answer += arr[weights[i]] * arr[weights[j]];
			}
		}
	}
	return answer;
}