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

< 해설 >

코딩테스트 초창기에 풀다가 못풀었던 나름 사연있는 문제.

보통 답으로 long long 을 요구하는 문제는 무지성 for문을 이용하면 시간초과가 나게 되어있다. 이거 나름 코딩테스트 꿀팁임.

동일한 몸무게에 대한 중복연산을 하지 않으려고 map을 사용했다.

map을 사용해서 요소 하나하나 비교하면서 2:4, 3:4, 2:3 의 비율을 가진 몸무게를 찾으면 된다.

 

여기서! 내가 헷갈렸던 부분.

만약 100짜리 몸무게를 가진 친구들이 4명이라고 하자. 그러면 100 몸무게를 가진 친구들끼리 시소를 탈 수 있는 값은 6번이 된다.

이해를 돕기 위한 그림

동일한 몸무게를 가진 친구들은 nC2, 즉 n * n-1 / 2를 해 주어야 한다.

그렇다면 만약 2:4를 만족하는 케이스인 100 과 200이 있다고 하자. 100 몸무게를 가진 친구가 2명, 200 몸무게를 가진 친구가 3명이라면 answer에는 2*3 인 6이 더해져야 한다. 나는 이거 안하고 그냥 answer += n 해서 오류파티 했음... ㄱ-

 

주어진 테스트 케이스로는 확인할 수 없는 부분이라 신경을 못쓴것 같다. 이 부분만 신경 쓴다면 금새 해결할 수 있을 것이다. (물론 난 몰라서 ㅈㄴ 오래 걸렸다.)

 

< 문제 >

어느 공원 놀이터에는 시소가 하나 설치되어 있습니다. 이 시소는 중심으로부터 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 <string>
#include <vector>
#include <map>

using namespace std;

long long solution(vector<int> weights) {
    long long answer = 0;
    map<long long, long long> weightMap;
    
    for(const auto& w :weights)
        weightMap[w]++;
    
    auto iter = weightMap.begin();
    while(iter != weightMap.end())
    {
        long long w = iter->first;

        // 2 : 3
        if (w % 2 == 0)
        {
            if (weightMap.find(w / 2 * 3) != weightMap.end())
                answer += weightMap[w / 2 * 3] * iter->second;
        }
        // 3 : 4
        if (w % 3 == 0)
        {
            if (weightMap.find(w / 3 * 4) != weightMap.end())
                answer += weightMap[w / 3 * 4] * iter->second;
        }
        // 2:4 -> 1:2
        if (weightMap.find(w * 2) != weightMap.end())
            answer += weightMap[w * 2] * iter->second;

        // 같은 경우
        if (weightMap[w] != 0)
            answer += (weightMap[w] * (weightMap[w]-1)) / 2;

        iter++;
    }
    
    return answer;
}