프로그래머스 | Level 2 | 시소 짝꿍
Programmers | Level 2 | 시소 짝꿍
Problems
- 📘 Src: Programmers
- 🗂️ Cat: Simulation
Description
어느 공원 놀이터에는 시소가 하나 설치되어 있습니다. 이 시소는 중심으로부터 2(m), 3(m), 4(m) 거리의 지점에 좌석이 하나씩 있습니다.
이 시소를 두 명이 마주 보고 탄다고 할 때, 시소가 평형인 상태에서 각각에 의해 시소에 걸리는 토크의 크기가 서로 상쇄되어 완전한 균형을 이룰 수 있다면 그 두 사람을 시소 짝꿍이라고 합니다. 즉, 탑승한 사람의 무게와 시소 축과 좌석 간의 거리의 곱이 양쪽 다 같다면 시소 짝꿍이라고 할 수 있습니다.
사람들의 몸무게 목록 weights이 주어질 때, 시소 짝꿍이 몇 쌍 존재하는지 구하여 return 하도록 solution 함수를 완성해주세요.
Constraints
- 2 ≤
weights의 길이 ≤ 100,000 - 100 ≤
weights[i]≤ 1,000 - 몸무게는 모두 정수이며, 단위는 N(뉴턴)입니다.
Examples
| weights | result |
|---|---|
| [100, 180, 360, 100, 270] | 4 |
Solutions
Code
import java.util.*;
class Solution {
public long solution(int[] weights) {
long pair = 0; // 시소 짝꿍이 될 수 있는 쌍의 수
Map<Double, Long> weightMap = new HashMap<>(); // 각 몸무게를 저장할 해시맵
// 모든 몸무게에 대해 시소 짝꿍을 찾는 과정
for (int weight : weights) {
// 현재 무게에 대해 가능한 시소 짝꿍의 비율들을 확인
pair += weightMap.getOrDefault(weight * 1.0, 0L); // 같은 무게
pair += weightMap.getOrDefault(weight * 2.0 / 3, 0L); // 비율 2:3
pair += weightMap.getOrDefault(weight * 3.0 / 2, 0L); // 비율 3:2
pair += weightMap.getOrDefault(weight / 2.0, 0L); // 비율 1:2
pair += weightMap.getOrDefault(weight * 2.0, 0L); // 비율 2:1
pair += weightMap.getOrDefault(weight * 3.0 / 4, 0L); // 비율 3:4
pair += weightMap.getOrDefault(weight * 4.0 / 3, 0L); // 비율 4:3
// 현재 무게를 해시맵에 저장하여 갱신
weightMap.put(weight * 1.0, weightMap.getOrDefault(weight * 1.0, 0L) + 1);
}
return pair; // 시소 짝꿍이 될 수 있는 쌍의 수 반환
}
}
Approach
이 문제는 주어진 몸무게 목록에서 시소 짝꿍이 될 수 있는 두 사람의 쌍을 찾는 문제입니다. 시소 짝꿍이란, 두 사람이 시소에 탔을 때 시소가 평형을 이루기 위해 두 사람의 토크가 같아야 한다는 것을 의미합니다. 이를 해결하기 위해, 각 몸무게에 대해 가능한 비율들을 확인하며 쌍을 찾는 방식으로 접근합니다.
1. 문제 분석
이 문제는 주어진 몸무게 배열에서 시소 짝꿍이 될 수 있는 쌍을 찾는 문제입니다. 시소 짝꿍이 성립하려면 두 사람의 몸무게와 시소 중심에서의 거리가 일정한 비율을 가져야 합니다. 이때, 시소에서 주어진 거리는 2, 3, 4(m)로 제한되며, 따라서 두 사람의 몸무게가 1:2, 2:1, 3:4, 4:3 등의 비율일 때 시소가 균형을 이룰 수 있습니다. 이를 바탕으로 가능한 모든 쌍을 찾고, 해당 비율이 만족되는 경우 시소 짝꿍으로 처리해야 합니다.
그러나 단순히 모든 몸무게 쌍을 비교하는 방식으로는 문제를 효율적으로 해결할 수 없습니다. 몸무게 배열의 길이가 최대 100,000까지 주어질 수 있으며, 두 사람 간의 모든 쌍을 비교하는 경우 100,000 x 100,000 / 2로 약 50억 개의 비교가 필요합니다. 이러한 비효율적인 방식 대신, 해시맵을 활용하여 쌍을 효율적으로 찾는 방법이 필요합니다. 해시맵을 사용하면 각 몸무게와 그 비율에 맞는 짝을 빠르게 탐색할 수 있어 시간 복잡도를 크게 줄일 수 있습니다.
따라서 문제를 해결하는 핵심은 주어진 몸무게 배열에서 가능한 비율을 해시맵을 통해 빠르게 찾고, 그에 맞는 쌍을 효율적으로 계산하는 데 있습니다.
2. 접근 방식
각 몸무게에 대해 가능한 모든 시소 짝꿍 비율을 확인하며, 쌍을 찾는 방식으로 문제를 해결할 수 있습니다. 이를 위해 다음과 같은 접근 방식을 사용합니다.
- 해시맵 활용: 각 몸무게에 대해 해시맵을 사용하여 해당 몸무게와 시소 짝꿍이 될 수 있는 비율의 몸무게를 저장합니다. 이를 통해 빠르게 쌍을 찾을 수 있습니다.
- 비율 계산: 두 사람이 시소 짝꿍이 될 수 있는 비율은 1:2, 2:1, 3:4, 4:3, 2:3, 3:2와 같은 다양한 비율로 주어집니다. 이를 해시맵에 저장하여, 현재 몸무게에 대해 가능한 비율을 모두 확인하고 쌍을 찾습니다.
3. 초기 변수 설정
시소 짝꿍이 될 수 있는 쌍의 개수를 저장하기 위해 변수를 초기화하고, 각 몸무게를 관리할 해시맵을 생성합니다.
배열의 길이가 최대 100,000일 수 있으므로, 두 사람을 짝으로 선택하는 경우 가능한 최대 쌍의 개수는 약 50억(4,999,950,000)입니다. 따라서 쌍의 개수를 저장하는 변수는 long 타입을 사용해 오버플로우를 방지합니다. 또한, 시소의 좌석 간 거리에 따라 몸무게 비율을 계산할 때 실수형 연산이 필요하므로, 해시맵의 키는 Double 타입으로 설정하여 정확한 계산을 할 수 있도록 합니다. 해시맵의 값은 각 몸무게가 등장한 횟수를 저장하는데, 값 역시 Long 타입을 사용해 대규모 데이터를 안전하게 처리합니다.
long pair = 0; // 시소 짝꿍이 될 수 있는 쌍의 수를 저장할 변수
Map<Double, Long> weightMap = new HashMap<>(); // 각 몸무게를 저장할 해시맵
4. 시소 짝꿍 탐색
주어진 몸무게 목록을 순회하며, 시소 짝꿍이 될 수 있는 비율을 기준으로 가능한 짝을 찾아냅니다. 시소가 균형을 이루려면 두 사람의 몸무게 비율이 정확히 일치해야 하므로, 이를 위해 소수점 단위까지 계산하여 정확한 비교를 합니다. 비율에 따라 해시맵에서 가능한 짝을 찾아 쌍을 형성합니다.
for (int weight : weights) {
pair += weightMap.getOrDefault(weight * 1.0, 0L); // 같은 무게
pair += weightMap.getOrDefault(weight * 2.0 / 3, 0L); // 비율 2:3
pair += weightMap.getOrDefault(weight * 3.0 / 2, 0L); // 비율 3:2
pair += weightMap.getOrDefault(weight / 2.0, 0L); // 비율 1:2
pair += weightMap.getOrDefault(weight * 2.0, 0L); // 비율 2:1
pair += weightMap.getOrDefault(weight * 3.0 / 4, 0L); // 비율 3:4
pair += weightMap.getOrDefault(weight * 4.0 / 3, 0L); // 비율 4:3
...
}
- 1 : 1 비율: 두 사람의 몸무게가 같을 때, 시소가 평형을 이룹니다. 이 경우 같은 몸무게를 해시맵에서 찾아 짝꿍을 찾습니다.
- 2 : 3 비율: 한 사람이 2m 좌석에, 다른 사람이 3m 좌석에 앉을 때, 두 사람의 몸무게 비율이 2:3이어야 평형을 이룹니다.
- 3 : 2 비율: 한 사람이 3m 좌석에, 다른 사람이 2m 좌석에 앉을 때, 두 사람의 몸무게 비율이 3:2이어야 시소가 평형을 이룹니다.
- 1 : 2 비율: 한 사람이 2m 좌석에, 다른 사람이 4m 좌석에 앉을 때, 두 사람의 몸무게 비율이 1:2이어야 평형을 이룹니다.
- 2 : 1 비율: 한 사람이 4m 좌석에, 다른 사람이 2m 좌석에 앉을 때, 두 사람의 몸무게 비율이 2:1이어야 평형을 이룹니다.
- 3 : 4 비율: 한 사람이 3m 좌석에, 다른 사람이 4m 좌석에 앉을 때, 두 사람의 몸무게 비율이 3:4이어야 평형을 이룹니다.
- 4 : 3 비율: 한 사람이 4m 좌석에, 다른 사람이 3m 좌석에 앉을 때, 두 사람의 몸무게 비율이 4:3이어야 평형을 이룹니다.
이 과정을 통해 현재 몸무게에 대해 가능한 모든 비율을 탐색하여 시소 짝꿍을 찾아내고, 그 수를 기록합니다.
5. 현재 몸무게 저장
현재 탐색 중인 몸무게를 해시맵에 저장하여, 이후에 시소 짝꿍이 될 수 있는 다른 몸무게들과 비교할 수 있도록 합니다. 동일한 몸무게가 여러 번 등장할 수 있기 때문에, 해시맵에 저장할 때마다 기존 값에 1을 더해 해당 몸무게의 등장 횟수를 갱신합니다. 이렇게 하면 동일한 비율을 이루는 다른 몸무게가 등장할 경우 빠르게 짝을 찾을 수 있습니다.
for (int weight : weights) {
...
// 현재 무게를 해시맵에 저장하여 갱신
weightMap.put(weight * 1.0, weightMap.getOrDefault(weight * 1.0, 0L) + 1);
}
6. 최종 결과 반환
모든 몸무게에 대한 탐색이 완료되면, 해시맵을 통해 찾은 모든 시소 짝꿍 쌍의 수를 반환합니다. 각 쌍은 앞서 계산된 비율에 따라 시소가 균형을 이루는 경우이며, 이 값이 최종 결과로 반환됩니다.
// 시소 짝꿍이 될 수 있는 쌍의 수 반환
return pair;
Complexity
- ⏳ TC: O(n)
- 💾 SC: O(n)
몸무게 목록을 한 번 순회하며, 각 몸무게에 대해 해시맵을 사용해 시소 짝꿍을 찾기 때문에 시간 복잡도는 O(n)입니다. 또한, 해시맵에 각 몸무게를 저장하므로 공간 복잡도 역시 O(n)입니다.
- Algorithm
- Simulation