[Programmers] 시소 짝꿍 / ❌

프로그래머스

 

1. 제출 코드 (1시간 2분 23초 / Dictionary)

import java.util.*;

class Solution {
    public long solution(int[] weights) {
        long answer = 0;
        Map<Double, Integer> map = new HashMap<>();
        Arrays.sort(weights);
        
        for(int weight : weights) {
            double a = (double) weight;
            double b = ((double) weight * 2.0) / 3.0;
            double c = ((double) weight * 2.0) / 4.0;
            double d = ((double) weight * 3.0) / 4.0;
            
            if(map.containsKey(a)) answer += map.get(a);
            if(map.containsKey(b)) answer += map.get(b);
            if(map.containsKey(c)) answer += map.get(c);
            if(map.containsKey(d)) answer += map.get(d);
            
            map.put((weight * 1.0), map.getOrDefault((weight * 1.0), 0) + 1);
        }
        return answer;
    }
}

 

2. 구현 로직

1. weights의 숫자를 오름차순으로 정렬한다.
2. for문으로 weights를 탐색한다.
   1. 오름차순이므로 정답이 되는 경우는 1:1 / 2:3 / 2:4 / 3:4인 경우 밖에 없으므로 값을 계산해준다.
   2. 만약 map에 정답 비율에 해당되는 값이 있다면 answer에 key의 value를 더해준다.
   3. map에 key는 weight 값을 넣어주고 만약 같은 수가 있을 경우도 있기에 map.get을 통해 value를 가져와서 +1을 해준다.

 

3. 풀이 회고

• 이번 문제도 weights의 크기가 100,000 이하로 시간복잡도 O(nlogn) 이하로 풀어야겠다고 생각했다.
• 알고리즘을 적용해야 풀 수 있을 거 같아서 계속해서 어떤 알고리즘을 적용할지 생각해 봤는데 떠오르지 않았다.
• 결국, 구글링을 통해 어떤 알고리즘이 적용되는지 검색했고 자료구조 Dictionary를 활용한다는 것을 알았다.
• 시간복잡도를 고려하고 계속해서 어떤 알고리즘을 사용할지 고민하는데 자료구조를 활용하여 문제 풀이가 가능하다는 점도 고려해야될 거 같다.