2025.4.15 알고리즘 코드카타

알고리즘 코드카타 - 121. 시소 짝꿍

문제 링크

문제 설명

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

using namespace std;

long long solution(vector<int> weights) {
    long long answer = 0;
    // 이중for문으로 충분할 듯
    // weights[i] weights[j]의 최소공배수를 구했을 때 둘중 큰 쪽*4 보다 크면 실패
    for(int i = 0; i < weights.size() - 1; i++)
    {
        for(int j = i+1; j<weights.size(); j++)
        {
            if(weights[i] == weights[j]) answer++;
            int l = lcm(weights[i], weights[j]);
            int bigger = max(weights[i], weights[j]);
            weights[i] > weights[j] ? bigger = weights[i] : bigger = weights[j];
            
            if(bigger * 4 >= l)
            {
                answer++;
            }
        }
    }
    return answer;
}

• 최소공배수를 이용하려는 방식
• 단순하게 최소공배수를 구해서 둘 중 더 무거운 사람 무게*4(제일 먼 자리가 4니까)를 구해서 그 이내면 될 거라고 생각했는데, 아니었다.
• {20, 80}이 주어질 때, 최소공배수는 80이다. 그리고 80*4 = 320으로 최소공배수가 이보다 작다. 하지만 20, 80은 시소짝꿍이 될 수 없다. 비율이 안 맞기 때문.
• 시소에는 2, 3, 4m 자리만 있고 1m 자리는 없으므로, 80이 제일 가까운 2m 자리에 앉고 20이 제일 먼 4m 자리에 앉아도 80 : 160으로 짝꿍이 될 수 없다.

풀이 코드

#include <string>
#include <vector>
#include <numeric>
#include <map>

using namespace std;

long long solution(vector<int> weights) {
    long long answer = 0;
    map<int, int> weightcounts;
    vector<vector<int>> ratios = {{1,1},{2,3},{2,4},{3,2},{3,4},{4,2},{4,3}};
    
    for(int weight : weights)
    {
        for(auto& rat : ratios)
        {
            int target = (long long)weight* rat[0] / rat[1];
            if((long long)weight*rat[0] % rat[1] == 0)
            {
                answer += weightcounts[target];
            }
        }
        weightcounts[weight]++;
    }
    return answer;
}

• 문제 풀이의 핵심은 몸무게 x가 주어졌을 때, 짝꿍을 이룰 수 있는 몸무게 후보군 역시 정해진다는 것이다. 후보군은 시소 자리에 따라서 2, 3, 4의 조합 + 같은 몸무게 & 같은 자리 이다.

• 이를 단순하게 보자면 아래와 같다.

  1. 주어진 weights를 순회
  2. ratios의 원소들을 이용해서 각 몸무게 weight의 짝꿍 후보를 구한다.
  3. 그리고 그 후보들이 weights에 포함되어 있는지 확인해본다.

• 하지만 위를 그대로 실행하면 삼중으로 for문을 써야 하고, weights의 최대 길이 10만은 삼중for문으로 시간 초과가 나기에 충분한 크기이다.

• 그래서 순회를 하되, std::map을 사용해 조회를 빠르게 하여 소요 시간을 줄일 수 있다.

  1. 순회도중 만나는 몸무게는 일단 맵에 넣는다.
  2. 순회도중 만나는 몸무게에 ratios의 원소를 곱해서 일치하는 값이 맵에 있는지 확인.
  3. 일치하는 값이 있으면 쌍을 이루는 것이므로 answer++.