쌓고 쌓다
[프로그래머스] 시소 짝꿍 C++ 풀이 및 해설 본문
https://school.programmers.co.kr/learn/courses/30/lessons/152996#
풀이 방법
- Map의 Key는 몸무게, Value는 그 몸무게를 가진 사람의 수이다.
- weights를 돌며 2:3, 2:4, 3:4 비율이 동일한 값을 찾는다.
- 그 값(몸무게)을 가진 수만큼 answer에 더한다.
- 몸무게가 1:1로 동일한 경우가 존재하므로 이 경우도 고려한다.
- 1:1로 동일한 몸무게 수가 N이라면 N(N-1)/2 경우의 수를 가질 수 있다.
- 2자리라면 한자리는 N명중 한명, 남은 한자리는 N-1명중 한명. 나열하는 방법이 두가지이므로 나누기 2 (순서 고려X 이므로)
- 이 부분에 사실 m[i]>=2 조건문이 없어도 통과된다. N이 1일때 (1*0)/2 = 0이므로 변화 없다.
이번 문제는 혼자 못풀겠어서... 다른 사람들의 풀이를 참고했다. 많이 참고한 글을 아래와 같다.
전체 코드
#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];
}
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 삼총사 C++ 풀이 및 해설 (0) | 2023.10.02 |
---|---|
[프로그래머스] 크기가 작은 부분 문자열 C++ 풀이 및 해설 (0) | 2023.09.23 |
[프로그래머스] 숫자 카드 나누기 C++ 풀이 및 해설 (0) | 2023.09.19 |
[프로그래머스] 마법의 엘리베이터 C++ 풀이 및 해설 (0) | 2023.09.13 |
[프로그래머스] 배달 C++ 풀이 및 해설 (0) | 2023.09.07 |
Comments