프로그래머스 lv2 - 시소 짝꿍

✏️ 문제 풀이

< 초기 접근 > 

- 최대공약수로 비율을 구하기

• 두 Weight의 최대공약수를 구한다.
• 최대공약수가 없는 경우 넘어간다.
• 최대공약수가 있는 경우 기존 무게에 각각의 비율을 적용해 일치하는 경우의 수를 찾아 카운트한다.

이 경우 모든 비교에 대해 반복을 돌면서 최대공약수를 구해야 하기 때문에 비효율적으로 느껴졌다.
(프로그래머스의 C++은 최대공약수를 구하는 함수 GCD)

 

< 최종 접근 >

굳이 최대공약수를 구할 필요없이 두 무게가 제시된 비율에 해당하는지 확인만 하면 된다.
따라서 더 간단한 방법을 사용하고자 했다.

X : Y = 2 : 3
3X = 2Y
3X/2 = Y

 

비교 대상 중 하나인  Weight에 비율을 곱하고 나누어 시소의 균형을 이룰 수 있는 Y를 구하는 것이다.

이분탐색 Binary Search 사용하기

이분 탐색에는 lower_bound라는 기능이 있다.
정렬된 배열에 대해서 특정 값 X가 처음 존재하는 위치를 반환한다.
주어진 비율을 충족하는 두 무게를 알고 있기 때문에 lower_bound를 통해서
이와 일치하는 원소의 개수를 카운트하면 되는 것이다.

1) 데이터 정렬하기

이분 탐색은 정렬된 데이터를 기반으로 하기 때문에 weights를 정렬한다.

    sort(weights.begin(), weights.end());

 

2) 비율을 만족하는 무게를 구한다.

int w2 = (weights[i] * b) / a;

 

3) 계산된 무게와 동일한 데이터의 개수를 센다.

//계산된 무게 w2와 일치하는 값이 처음있는 위치를 찾기
auto it = lower_bound(weights.begin() + i + 1, weights.end(), w2);
//데이터의 끝이 아니고, 계산된 무게와 동일할 때까지
while (it != weights.end() && *it == w2) {
    answer++; //개수 카운트
    it++;     //다음 위치로 이동
}

upper_bound를 사용해서 계산된 무게와 일치하는 값이 가장 마지막에 있는 위치를 가져와 while문을 돌 수도 있다.

 

🖥️ 전체 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

long long solution(vector<int> weights) {
    long long answer = 0;
    
    sort(weights.begin(), weights.end());
    
    vector<pair<int, int>> ratios = {{1, 1}, {2, 3}, {2, 4}, {3, 4}};
    
     for (int i = 0; i < weights.size(); i++) {
        for (auto &[a, b] : ratios) {
            int w2 = (weights[i] * b) / a;
            if ((weights[i] * b) % a == 0) { //딱 나눠 떨어지면
                auto it = lower_bound(weights.begin() + i + 1, weights.end(), w2);
                while (it != weights.end() && *it == w2) {
                    answer++;
                    it++;
                }
            }
        }
    }
    
    return answer;
}