✍️Today I Learned

📅 2025-10-21

• 프로그래머스: 시소 짝꿍

---

프로그래머스: 시소 짝꿍

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

제한 사항

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

이전 풀이

모든 쌍을 계산하여 시간복잡도가 O(N^2)으로 시간 초과가 됐다.

#include <vector>
using namespace std;
long long solution(vector<int> weights) {
    long long answer = 0;
    vector<int> seesaw = {2,3,4};
    int idx = 0;
    while(idx<weights.size())
    {
        int temp = weights[idx];
        for(int i = idx + 1; i < weights.size(); i++)
        {
            if(temp == weights[i])
            {
                answer += 1;
                continue;
            }
            for(const int& dist1 : seesaw)
            {
                for(const int& dist2 : seesaw)
                {
                    if(temp*dist1%dist2 != 0) continue;
                    if(temp*dist1/dist2 < weights[i]) break;
                    if(temp*dist1/dist2 == weights[i])
                    {
                        answer += 1;
                        break;
                    }
                }
            }
        }
        idx += 1;
    }
    return answer;
}

최종 풀이

몸무게가 같은 경우의 조합 수를 먼저 계산 후 몸무게 별로 거리에 따른 조합 계산하여 시간복잡도를 O(N)으로 줄였다.

#include <vector>
#include <unordered_map>

using namespace std;

long long solution(vector<int> weights) {
    long long answer = 0;
    unordered_map<int, long long> weightCount;
    
    // 몸무게별 인원 수
    for(const int& i : weights)
    {
        weightCount[i] += 1;
    }
    // 같은 몸무게 조합 수
    for(const auto& [w,c] : weightCount)
    {
        if(c>1)
        {
            answer+=c*(c-1)/2;
        }
    }
    
    for(const auto& [w,c] : weightCount)
    {
        // 2:3
        if(w * 2 % 3 == 0)
        {
            int temp = w * 2 / 3;
            if(weightCount.find(temp) != weightCount.end())
            {
                answer += c * weightCount[temp];
            }
        }                
        // 2:4
        if(w * 2 % 4 == 0)
        {
            int temp = w * 2 / 4;
            if(weightCount.find(temp) != weightCount.end())
            {
                answer += c * weightCount[temp];
            }
        }
        // 3:4
        if(w * 3 % 4 == 0)
        {
            int temp = w * 3 / 4;
            if(weightCount.find(temp) != weightCount.end())
            {
                answer += c * weightCount[temp];
            }
        }
    }
    
    return answer;
}

---

💡 느낀 점 (What I Felt)

---

출처 프로그래머스: 시소 짝꿍