[Programmers] 시소 짝꿍

1. Link

https://school.programmers.co.kr/learn/courses/30/lessons/152996?language=cpp

2. 풀이 과정

1. 2,3,4(m) 만큼 떨어져서 시소에 앉을 수 있음 -> 정렬

• 그냥 문제를 단순하게 2중 for문으로 구현할 생각을 해 봤지만, 조건에서 100000 * 100000(100억 연산으로 무조건 시간 초과) 연산임을 보고 바로 방향을 틀었습니다.

• 다음으로는 입출력 예시가 비정렬 상태임을 확인하고 정렬 후 vector v[1001]에 배수 단위로 대입할까도 생각했습니다.

• 그런데, (2,3,4)를 잘 조합해보면 조합 결과가 다음과 같습니다.
  

  즉 4가지 경우의 수만 고려하면 된다는 뜻이며, 위 조건에서 각 배열값이 넘어서는 안되는 최댓값을 동시에 암시합니다.
  가령, 비교 숫자가 300일 경우를 가정하겠습니다. 그럴 경우 조건에 맞게 비교 시 나올 수 있는 수는 다음과 같습니다.
  
  여기서 300이란 값은 최대 600까지만 비교 가능하다는 이야기입니다. 즉, 1:2 비율을 넘는 수에 대해서는 비교할 필요조차 없음을 알 수 있습니다.

  따라서 정렬 후 for문을 돌리며 각 배열값이 이후의 값과 2배 이상 차이가 날 경우 바로 다음 배열값 비교를 시작하는 방식으로 구현합니다.
  2배 차이가 나기 전까지는 bool함수를 통해 위 조건(4가지)에 포함되는지 확인하는 것으로 코드를 마칩니다.
  

3. 정답 코드

#include <string>
#include <vector>
#include <algorithm>
#define ll long long

using namespace std;

bool isOkay(int x, int y){
    if(x == y) return true;
    if(x > y) swap(x, y);
    if(3 * x == 2 * y || 2 * x == y || 4 * x == 3 * y) return true;
    return false;
}

ll solution(vector<int> weights) {
    ll answer = 0;
    sort(weights.begin(), weights.end());
    for(int i=0;i<weights.size() - 1;++i){
        int a = weights[i], b = weights[i + 1];
        for(int j = i + 1;j<weights.size();){
            if(2 * a < b) break;
            answer += isOkay(a, b);
            b = weights[++j];
        }
    }    
    return answer;
}

4. 추천 음악

Taylor Swift - We are never ever getting back together

Link: https://www.youtube.com/watch?v=WA4iX5D9Z64

별 생각없이 노래 듣고 있었는데, 우연히 귀에 박혀 찾아보니 10년도 넘은 노래였다.. 예전에 참 많이 들었던 노래였는데 감회가 새롭네요