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

https://school.programmers.co.kr/learn/courses/30/lessons/152996

- 출처 : 프로그래머스 코딩 테스트 연습

프로그래머스

 

[문제 요약]

- 어느 공원 놀이터에는 시소가 하나 설치되어 있습니다.

- 이 시소는 중심으로부터 2(m), 3(m), 4(m) 거리의 지점에 좌석이 하나씩 있습니다.
이 시소를 두 명이 마주 보고 탄다고 할 때, 시소가 평형인 상태에서 각각에 의해 시소에 걸리는 토크의 크기가 서로 상쇄되어 완전한 균형을 이룰 수 있다면 그 두 사람을 시소 짝꿍이라고 합니다.

- 즉, 탑승한 사람의 무게와 시소 축과 좌석 간의 거리의 곱이 양쪽 다 같다면 시소 짝꿍이라고 할 수 있습니다.
- 사람들의 몸무게 목록 weights이 주어질 때, 시소 짝꿍이 몇 쌍 존재하는지 구하여 return 하도록 solution 함수를 완성해주세요.

 

[문제 조건]

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

[문제 풀이]

문제는 아주 간단하다.

 

예를들어 weights[i]의 사람의 짝꿍을 찾고 싶으면 weights[i] : x = (2 : 3 or 2 : 4 or 3 : 4)에 해당하는 x를 찾으면 된다. 

 

또한 weights[i]와 몸무게가 같은 사람이 짝꿍이 될 수도 있다. 

따라서 필자는 다음과 같은 방법을 이용했다.

• 주어지는 몸무게의 범위가 최대 1000이기 때문에 cnt[] 배열을 하나 두어서 각 몸무게 별 갯수를 세어준다.
• weights 배열을 하나씩 확인하면서 (2:3) , (2:4) , (3:4) 비율에 해당하는 몸무게의 개수만큼 정답에 더해준다.
• 몸무게가 같은 사람이 있는 경우는 조합을 이용하여 (n * (n-1) / 2) 공식을 이용하여 경우의 수를 세어준다. 이때의 값은 int범위를 넘어가기 때문에 long long 자료형으로 처리해준다.

 

[소스 코드]

#include <string>
#include <iostream>
#include <vector>

using namespace std;

long long solution(vector<int> weights) {
    long long answer = 0;

    vector<long long> cnt(1001,0);
    for(int i=0; i<weights.size(); i++)
        cnt[weights[i]]++;
    
    for(int i=0; i<weights.size(); i++)
    {
        //2:3
        if(weights[i]%2==0)
        {
            long long base = (weights[i]/2) * 3;
            if(base <= 1000) answer+=cnt[base];
        }
        //3:4
        if(weights[i]%3==0)
        {
            long long base = (weights[i]/3) * 4;
            if(base <= 1000) answer+=cnt[base];
        }
        
        //1:2
        long long base = weights[i] * 2;
        if(base <= 1000) answer+=cnt[base];
    }
    
    for(int i=100; i<=1000; i++)
    {
        if(cnt[i] >= 2)
            answer += (long long)(cnt[i] * (cnt[i]-1))/2;
    }
    
    return answer;
}

굳