728x90
코드 힌트
1. 빠르게 탐색할 수 있는 자료구조
- 처음 문제를 풀었을 때는 2중 for문을 사용하여 풀었지만, 시간이 많이 소요되어 시간 복잡도 문제가 발생했습니다.
- 빠르게 요소를 찾기 위해 이진 탐색을 사용하는 방법을 고려했습니다.
- 여기서는 HashMap을 사용하여 key는 요소(무게), value는 해당 요소의 빈도로 활용하여 문제를 풀었습니다.
2. 짝꿍 맞추기
- 시소 짝꿍이 되는 조건은 두 무게가 같은 비율일 때입니다.
- 예를 들어, 무게가 2(m), 3(m), 4(m)인 지점에 좌석이 있을 때, 두 좌석 간의 비율이 같으면 짝꿍이 됩니다.
- 즉, w1 * {2, 3, 4} == w2 * {2, 3, 4} 조건 중 하나라도 만족하면 짝꿍을 찾을 수 있습니다.
3. 중복 허용
- 만약 같은 무게를 가진 사람이 여러 명 있으면, 각 쌍을 조합하여 여러 짝꿍을 만들 수 있습니다.
- 예를 들어, 무게가 100인 사람이 3명이라면:
- [a: 100, b: 100, c: 100]
- a와 b, a와 c, b와 c가 짝꿍이 되어 총 3번의 짝꿍이 생깁니다.
- 중복된 무게를 효과적으로 관리하는 것이 중요합니다.
4. 타입 관리
- 2, 3, 4(m) 인 지점을 비교할 때 double로 변환한 후 int로 변경을 했을 때 문제가 발생할 수 있습니다.
- 처음부터 무게를 double로 변경하고 진행하시면 수월하게 관리할 수 있습니다.
정답은 더보기 클릭
더보기
import java.util.*;
class Solution {
public long solution(int[] arr) {
// weights 배열 생성 (int 배열을 double 배열로 변환)
double[] weights = new double[arr.length];
// arr 배열의 요소를 weights 배열로 복사
for (int i = 0; i < arr.length; i++) {
weights[i] = (double) arr[i];
}
// 결과를 저장할 변수
long result = 0;
// 무게와 해당 무게의 개수를 저장할 HashMap 생성
Map<Double,Integer> map = new HashMap<>();
// weights 배열을 순회하며 각 무게의 개수를 카운트하여 map에 저장
for (double weight : weights) {
map.put(weight, map.getOrDefault(weight, 0) + 1);
}
// weights 배열을 정렬하여 오름차순으로 정렬된 무게를 기준으로 탐색
Arrays.sort(weights);
// 정렬된 weights 배열을 순회하면서 짝꿍을 찾음
for (double weight : weights) {
// 현재 weight가 map에서 1인 경우 삭제, 그렇지 않으면 1 감소
if (map.get(weight) == 1) {
map.remove(weight);
} else {
map.put(weight, map.get(weight) - 1);
}
// 시소 짝꿍 조건에 맞는 값을 찾아 result에 더함
// 1. 같은 무게의 개수
result += map.getOrDefault(weight, 0);
// 2. 2배의 무게가 있는지 확인
result += map.getOrDefault(weight * 2, 0);
// 3. 4/3 배의 무게가 있는지 확인
result += map.getOrDefault(weight * 4. / 3, 0);
// 4. 3/2 배의 무게가 있는지 확인
result += map.getOrDefault(weight * 3. / 2, 0);
}
// 최종 결과 반환
return result;
}
}
728x90
'프로그래머스(Java) > Level 2' 카테고리의 다른 글
[프로그래머스] [PCCP 기출문제] 3번 / 충돌위험 찾기 (1) | 2024.10.09 |
---|---|
[프로그래머스] 호텔 대실 (1) | 2024.10.05 |
[프로그래머스] 마법의 엘리베이터 (2) | 2024.10.02 |
[프로그래머스] [PCCP 기출문제] 2번 / 퍼즐 게임 챌린지 (4) | 2024.10.01 |
[프로그래머스] 연속된 부분 수열의 합 (0) | 2024.09.25 |