[C++]/프로그래머스 시소 짝꿍

• 문제

어느 공원 놀이터에는 시소가 하나 설치되어 있습니다. 이 시소는 중심으로부터 2(m), 3(m), 4(m) 거리의 지점에 좌석이 하나씩 있습니다.
이 시소를 두 명이 마주 보고 탄다고 할 때, 시소가 평형인 상태에서 각각에 의해 시소에 걸리는 토크의 크기가 서로 상쇄되어 완전한 균형을 이룰 수 있다면 그 두 사람을 시소 짝꿍이라고 합니다. 즉, 탑승한 사람의 무게와 시소 축과 좌석 간의 거리의 곱이 양쪽 다 같다면 시소 짝꿍이라고 할 수 있습니다.
사람들의 몸무게 목록 weights이 주어질 때, 시소 짝꿍이 몇 쌍 존재하는지 구하여 return 하도록 solution 함수를 완성해주세요.

• 제한사항

2 ≤ weights의 길이 ≤ 100,000
100 ≤ weights[i] ≤ 1,000
몸무게 단위는 N(뉴턴)으로 주어집니다.
몸무게는 모두 정수입니다.

• 입출력 예

           weights               result
[100,180,360,100,270]     4

• 입출력 예 설명

{100, 100} 은 서로 같은 거리에 마주보고 앉으면 균형을 이룹니다.
{180, 360} 은 각각 4(m), 2(m) 거리에 마주보고 앉으면 균형을 이룹니다.
{180, 270} 은 각각 3(m), 2(m) 거리에 마주보고 앉으면 균형을 이룹니다.
{270, 360} 은 각각 4(m), 3(m) 거리에 마주보고 앉으면 균형을 이룹니다.

• 접근방식

일반적인 완전탐색으로 접근했다가 시간초과가 나서 정렬후 다시 시도하였다.

• 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

long long solution(vector<int> weights)
{
    long long answer = 0;
    // weights를 먼저 정렬하기 (정렬된 배열을 사용하면 순차적으로 비교할 때 시간 복잡도 감소)
    sort(weights.begin(), weights.end());

    // 완전 탐색을 통해 4:2, 4:3, 3:2, 1:1인 경우의 수 찾기
    for (int i = 0; i < weights.size(); i++)
    {
        for (int j = i + 1; j < weights.size(); j++)
        {
            if (weights[i] * 4 == weights[j] * 2 ||
                weights[i] * 4 == weights[j] * 3 ||
                weights[i] * 3 == weights[j] * 2 ||
                weights[i] == weights[j])
            {
                answer++;
            }
        }
    }

    return answer;
}

 

• 문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/152996

프로그래머스