문제 152996. 시소 짝꿍

문제 링크

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

프로그래머스

 

 

난이도 : Lv.2

 

문제 요약 설명

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

입력

• 사람들의 몸무게 목록 weights

입력 제한

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

입력 예제

// input
[100,180,360,100,270]

// ans
4

 

풀이 방식

이 문제를 풀기 전에 두 가지 사실을 알아내야한다. 두 가지 사실은 다음과 같다.

1. 같은 몸무게를 가진 사람들이 다른 위치에 앉아 평행한 경우들은 하나의 시소 짝꿍으로 취급하지만, 다른 몸무게를 가진 사람들이 (A:100, C:150) (B:100, C:150)와 같이 같은 몸무게 쌍이여도 사람이 다르면 서로 다른 시소 짝꿍으로 취급한다.
2. 각각의 사람들은 2m, 3m, 4m에 앉을 수 있기 때문에 두 사람이 앉는 경우 3*3=9가지의 경우의 수가 나오지만, 서로 다른 몸무게인 경우는 한 가지, 같은 몸무게를 가진 경우는 항상 3가지의 경우만 평행할 수 있다. 

위 두 가지 사실을 통해 임의의 뉴턴 X를 가진 경우의 수가 n개라면 임의의 뉴턴 X 에서 시소 짝꿍의 수가 nC2라는 것을 알 수 있다. 문제는 같은 몸무게를 가진 사람이 존재할 경우 2가지의 중복된 경우의 수가 발생한다는 것이다. 따라서, 이를 해결하기 위해 중복된 경우의 수만큼 빼줘야하며, 앉을 수 있는 위치가 총 3가지( 2m, 3m, 4m)이므로 같은 몸무게를 가진 사람의 수 * 2만큼 경우의 수를 빼주면 된다. 

정답 코드 

#include <string>
#include <vector>
#include <bits/stdc++.h>

#define MAXW 1000

using namespace std;

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

    sort(weights.begin(), weights.end());

    vector<int> v1(MAXW*4 + 1);
    
    for (int w : weights) {
        
        v1[w * 2]++; v1[w * 3]++; v1[w * 4]++;

        if (prev_w == w) {
            same_w_cnt++;
            answer -= same_w_cnt * 2; 
        } else {
            prev_w = w;
            same_w_cnt = 0;
        }
    }

    for (long long elem : v1) {
        //if(elem > 0) cout << elem << ' ';
        
        if (elem > 1) {
            answer += elem * (elem - 1) / 2;
        }
    }

    return answer;
}