https://school.programmers.co.kr/learn/courses/30/lessons/152996
문제요점
- 4,3,2 축 2,3,4
- 시소짝꿍: 몸무게*거리가 같으면
- 몇쌍 짝꿍존재?
- (보충) 짝꿍끼리의 순서는 상관없다. (시소의 오른쪽, 왼쪽 중 어디에 앉는지는 구별하지 않음)
풀이
- 2,3,4를 통해 가능한 조합을 만든다
- 짝꿍끼리의 순서는 상관없으므로 왼쪽무게 중심으로 가능한 오른쪽 무게를 찾고 그 갯수를 더한다
- 왼쪽 중심으로 가능한 오른쪽무게는 왼쪽무게의 *1, *3/2, *2, *4/3이다
- 왼쪽이 2, 오른쪽 2일때 => 1:1 => 오른쪽은 왼쪽의 1배
- 왼쪽이 2, 오른쪽 3일때 => 2:3 => 오른쪽은 왼쪽의 3/2배
- 왼쪽이 2, 오른쪽 4일때 => 1:2 => 오른쪽은 왼쪽의 2배
- 왼쪽이 3, 오른쪽 4일때 => 3:4 => 오른쪽은 왼쪽의 4/3배
- 몸무게마다 갯수를 hash로 정리
- 왼쪽을 기준으로 더 큰 무게(오른쪽)를 찾아야하니까 몸무게를 오름차순 sort한다
- weights를 순회하며 왼쪽 몸무게가 각 weight일 때마다 가능한 오른쪽 몸무게가 있으면 answer에 추가한다
- left, right 같은 몸무게이면 자신을 제외한 갯수를 추가한다
- 다른 가능한 몸무게가 존재하면 갯수를 추가한다
- 짝꿍끼리의 순서는 상관없으므로 다음차례에선 현재무게를 비교대상에서 제외시킨다.
각 weight마다 위 4가지 비율의 무게를 구한 뒤 weights에 있는지 찾아봐야하는데 hash 를 사용하면 빠르다 o(1)
hash에 각 무게가 있음 answer에 더해준다
ab = ba는 같다. 이처럼 짝꿍끼리의 순서는 상관없으므로 다음차례에선 현재무게를 비교대상에서 제외시킨다.
전체코드
function solution(weights) {
var answer = 0;
const hash = {}; // {weight: count} 수가 존재하는지 O(1)로 찾기위해 해쉬를 썼다.
for (const w of weights) {
hash[w] = (hash[w] || 0 ) + 1;
}
weights.sort((a, b) => a-b);
for (const w of weights) {
if (hash[w] > 1) answer += hash[w]-1; // 자신과 똑같은 수가 있으면, 자신을 제외한 짝꿍의 수를 더한다.
if (hash[w*3/2] > 0) answer += hash[w*3/2]; // 자신보다 3/2배 큰 수가 있음 그 수만큼 더한다
if (hash[w*2] > 0) answer += hash[w*2]; // 자신보다 2배 큰 수가 있음 그 수 만큼 더한다.
if (hash[w*4/3] > 0) answer += hash[w*4/3];
hash[w] -= 1; // 짝꿍끼리의 순서는 상관없다 따라서 다음차례에서 현재 w를 비교대상에서 제외시킨다
}
return answer;
}
또 다른 풀이
unction solution(weights) {
var answer = 0;
const possibles = [1, 3 / 2, 2, 4 / 3];
const obj = {};
weights.forEach((weight) => {
obj[weight] = (obj[weight] || 0) + 1;
});
weights.sort((a, b) => a - b);
for (const leftW of weights) {
for (const p of possibles) {
const rightW = leftW * p;
// 같은 몸무게이면
if (leftW === rightW) {
answer += obj[leftW] - 1; // 자신을 제외한 몸무게 갯수를 더한다
} else if (obj[rightW]) {
answer += obj[rightW]; // 가능한 몸무게의 갯수를 더한다
}
}
obj[leftW]--;
}
return answer;
}
