코딩 테스트 연습

프로그래머스 - 시소 짝꿍

이전 풀이 코드

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

using namespace std;

// 최대 공약수
int gcd(int a,int b)
{
    int temp;
    while(a%b!=0)
    {
        int temp=a%b;
        a=b;
        b=temp;
    }
    return b;
}

// 최소 공배수
int lcm(int a,int b)
{
    return a*b/gcd(a,b);
}

long long solution(vector<int> weights) {
    long long answer = 0;
    
    map<int,int> weight_cnt;
    for(int i=0;i<weights.size();i++)
        weight_cnt[weights[i]]++;
    
    map<int,int>::iterator m=weight_cnt.begin();
    for(;m!=weight_cnt.end();m++)
    {
        if(m->second==2)
        {
            answer++;
        }
        else if(m->second>2)
        {
            for(int i=m->second-1;i>0;i--)
                answer+=i;
        }
    
        map<int,int>::iterator m2=m;
        m2++;
        for(;m2!=weight_cnt.end();m2++)
        {
            if(m->first!=m2->first)
            {
                int now_lcm=lcm(m->first,m2->first);
                
                if(now_lcm==(m2->first))
                {
                    now_lcm*=2;// 만약 한쪽의 값과 최소공배수가 같다면 시소에서의 최소값인 *2를 해준다
                }
                // 최소공배수에 두 수 중 작은 수를 나누었을 대 그 몫이 4이하라면 2~4배 중 하나라는 것, 다른쪽 수도 마찬가지가 됨
                if(now_lcm/min(m->first,m2->first)<=4)
                {
                    answer+=m->second*m2->second;
                }
            }
        }
    }
    return answer;
}

---

이 문제는 이전에 풀었던 기록이 있네요.

최대한 안 보고 진행해야겠네요.

이미 최소 공배수를 구하는 내용을 봐버리긴 했지만요.

문제에서 공배수를 쓰는 게 좋다는 것을 알려주는 것 같네요,

시소가 평형을 이루도록 앉을 수 있는 한 쌍의 수를 구하는 문제인데, 이 때 힘의 양은 무게 * 거리가 되네요.

무게 A 거리(2/3/4) == 무게 B 거리(2/3/4)

두 무게의 최소 공배수를 구한 뒤 그 공배수가 무게 A, 무게 B의 2,3,4 배이면 한 쌍을 이룰 수 있는 겁니다.

1차 코드

#include <string>
#include <vector>

using namespace std;

int GetGCD(int a, int b)
{
    return (a % b) ? GetGCD(b, a % b) : b;
}

long long GetLCM(int a, int b)
{
    return (long long)a * b / GetGCD(a, b);
}

long long solution(vector<int> weights) {
    long long answer = 0;
    
    for(int i = 0; i < weights.size(); i++)
    {
        for(int j = i + 1; j < weights.size(); j++)
        {
            int first = weights[i];
            int second = weights[j];
            
            if(first == second)
            {
                answer++;
            }
            else
            {
                long long lcm = GetLCM(first, second);
                
                int distA = lcm / first;
                int distB = lcm / second;
                
                if((distA == 1 && distB == 2) ||
                   (distB == 1 && distA == 2))
                {
                    answer++;
                }
                else if((distA <= 4 && distA >= 2)
                       && (distB <= 4 && distB >=2))
                {
                    answer++;
                }
            }
        }
    }
    return answer;
}

예외처리를 어떻게 작성해야 할지 고민했습니다. 그냥 하드코딩하게 됬네요.
제출해본 결과 대부분 시간초과가 발생했습니다.
오답은 없는데 시간초과가 문제네요. N^2의 시간 복잡도는 역시 안 되나 봅니다.

---

시간 복잡도를 줄일 방법이 없을까 고민하다 생각이 안나 이전 코드를 확인했습니다.
map으로 무게당 수를 기록한 뒤 같은 무게에 대해서는 중복 연산을 막는 방법을 사용했네요.
아 왜 이걸 생각 못했지?