[프로그래머스] 시소 짝꿍 / gcd 최대공약수, lcm 최소공배수

 

Level. 2

 

문제

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

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

 

풀이

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

using namespace std;

// 시소는 중심으로부터 2(m), 3(m), 4(m) 거리! 1m는 없음

// 최대공약수 : greatest common factor
long long gcd(int a, int b){
    if(a%b==0) return b;
    return gcd(b, a%b);
}

// 최소공배수 : least common multiple
long long lcm(int a, int b){
    return a*b/gcd(a,b);
}

long long solution(vector<int> weights) {
    long long answer = 0;
    long long l;
    map<int, int> map;
    for(int weight : weights){
        map[weight] += 1;
    }
    
    for(auto i : map){

        for(int n=1; n<i.second; n++)
            answer += n;
        
        for(auto j:map){
            if(j.first != i.first){
                l = lcm(j.first, i.first);
                // 1m는 없으므로 2를 곱해준다. (j.first의 위치 1m -> 2m)
                if(l == j.first) l *= 2;
                if(l/i.first <= 4) answer += i.second * j.second;
            }
        }
        
        map.erase(i.first);

    }
    
    return answer;
}

 

해결방법

1. map 자료구조에 몸무게별로 count를 저장해주었다.
2. map을 탐색하며 시소짝꿍 개수를 구해 answer에 더해준다.
   • 같은 몸무게끼리 시소짝꿍의 개수를 구한다.
   • 다른 몸무게끼리 시소짝궁의 갯수를 구하는데, 두 몸무게의 최소공배수가 큰 몸무게(j.first)와 동일할 경우 1m에는 좌석이 없으므로 최소공배수에 2를 곱해준다. 
     최종 구해진 최소공배수가 작은 몸무게(i.first)로 나누었을 때 4 이하일 경우 각각의 count를 곱한 수를 더해준다. 
     
     

풀이 2. - 같은 몸무게끼리의 시소짝궁 갯수 구하는 법 수정

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

using namespace std;

long long gcd(int a, int b){
    if(a%b==0) return b;
    return gcd(b, a%b);
}

// 최소공배수 : least common multiple
long long lcm(int a, int b){
    return a*b/gcd(a,b);
}

long long solution(vector<int> weights) {
    long long answer = 0;
    long long l;
    map<int, long long> map;
    for(int weight : weights){
        map[weight] += 1;
    }
    
    for(auto i : map){

        // 같은 몸무게가 여럿인 경우
        answer += i.second*(i.second-1)/2;
        
        for(auto j:map){
            if(j.first != i.first){
                l = lcm(j.first, i.first);
                if(l == j.first) l *= 2;
                if(l/i.first <= 4) answer += i.second * j.second;
            }
        }
        map.erase(i.first);
    }
    return answer;
}

 

 

---

다른 풀이

#include <string>
#include <vector>

using namespace std;

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

    vector<long long> arr(2001,0);

    for(const auto v : weights)
    {
        arr[v]++;
    }

    for(int i = 100; i <= 1000; ++i)
    {
        if(arr[i] == 0)
        {
            continue;
        }

        answer += arr[i]*(arr[i]-1) / 2;
		
        // 2m : 4m
        answer += arr[i] * arr[2 * i];
		
        // 2m : 3m
        if((i * 3) % 2 == 0)
        {
            answer += arr[i] * arr[i * 3 / 2];
        }
		
        // 3m : 4m
        if((i * 4) % 3 == 0)
        {
            answer += arr[i] * arr[i * 4 / 3];
        }   
    }

    return answer;
}

 

1. 미리 몸무게 별로 count를 저장한 배열을 구해 준 후 
2. 몸무게 범위만큼 반복문을 돌려주었다. (100 ≤ weights[i] ≤ 1,000)
3. 반복문을 돌 때마다 아래 경우의 수의 개수를 answer에 더해주었다. 
   • 1. 몸무게가 같을 경우의 시소짝꿍 수
   • 2. 2m : 4m 거리의 시소짝궁 수 
   • 3. 2m : 3m 거리의 시소짝궁 수 
   • 4. 3m : 4m 거리의 시소짝궁 수 

 

 

 

 

---

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

프로그래머스