[프로그래머스] 시소 짝꿍 C++ 풀이 및 해설

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

프로그래머스

풀이 방법

1. Map의 Key는 몸무게, Value는 그 몸무게를 가진 사람의 수이다.
2. weights를 돌며 2:3, 2:4, 3:4 비율이 동일한 값을 찾는다.
3. 그 값(몸무게)을 가진 수만큼 answer에 더한다.
4. 몸무게가 1:1로 동일한 경우가 존재하므로 이 경우도 고려한다.
   1. 1:1로 동일한 몸무게 수가 N이라면 N(N-1)/2 경우의 수를 가질 수 있다. 
   2. 2자리라면 한자리는 N명중 한명, 남은 한자리는 N-1명중 한명. 나열하는 방법이 두가지이므로 나누기 2 (순서 고려X 이므로)
   3. 이 부분에 사실 m[i]>=2 조건문이 없어도 통과된다. N이 1일때 (1*0)/2 = 0이므로 변화 없다.

 

 

 

이번 문제는 혼자 못풀겠어서... 다른 사람들의 풀이를 참고했다. 많이 참고한 글을 아래와 같다.

https://velog.io/@rlagksql219/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4C-%EC%8B%9C%EC%86%8C-%EC%A7%9D%EA%BF%8D

[프로그래머스/C++] 시소 짝꿍

 

전체 코드

#include <string>
#include <vector>
#include <iostream>
#include <map>
using namespace std;

long long solution(vector<int> weights) {
    long long answer = 0;
    map<int, long long> m;
    // m.find 반환값은 iterator이며 ->first는 Key, ->second는 Value이다.
    for(int i=0; i<weights.size(); i++) {
        if(m.find(weights[i])!=m.end())
            m[weights[i]]++;
        else
            m.insert({weights[i], 1});
    }
    
    for(int i=0; i<weights.size(); i++) {
        long long base = 0;
        
        base = weights[i]*2;
        if(base%3==0 && m.find(base/3)!=m.end()) {
            answer+= m[base/3];
        }

        if(base%4==0 && m.find(base/4)!=m.end())
            answer+=m[base/4];

        base = weights[i]*3;
        if(base%4==0 && m.find(base/4)!=m.end())
            answer+=m[base/4];
    }
    
    for(int i=100; i<=1000; i++) {
        if(m[i]>=2)
            answer+=(m[i]*(m[i]-1))/2;
    }
    
    return answer;
}

 

 

아래의 코드로 짰다가 삽질을 많이했다.

몸무게들을 담은 Map을 통해서 문제를 풀 수 있을 것 같았지만

예를 들어 [180, 360, 180, 360]처럼

{180, 360}은 4 2로 균형을 이룬다.

{360, 180}은 2 4로 균형을 이룬다.

하지만 아래의 코드는 2 4 비율만을 계산하기에 문제가 된다.

    map<int, long long>::iterator iter;
    for(iter = m.begin(); iter!=m.end(); iter++) {
        long long base = 0;
        
        base = iter->second;
        // 중복된 키의 개수가 2이상이라면
        if(base>=2) {
            cout<<(long long)((base*(base-1))/2)<<endl;
            answer+=(long long)((base*(base-1))/2);
        }
        
        base = iter->first*2;
        if(base%3==0 && m.find(base/3)!=m.end()) {
            answer+= m[base/3];
        }

        if(base%4==0 && m.find(base/4)!=m.end())
            answer+=m[base/4];

        base = iter->first*3;
        if(base%4==0 && m.find(base/4)!=m.end())
            answer+=m[base/4];
    }