프로그래머스, 시소 짝꿍

문제 설명

중심으로 부터 2(m), 3(m), 4(m) 거리의 지점에 좌석이 하나씩 놓여 있다. 각 몸무게가 주어질 때 시소가 평행하는 경우를 구하는 문제이다.

https://school.programmers.co.kr/learn/courses/30/lessons/152996

프로그래머스

문제 풀이

첫 번째 접근

weights의 최대 길이가 100,000이라 2차원 반복문으로 풀면 시간 복잡도가 난다. 그렇다면 1차원 반복문으로 승부를 봐야 한다는 건데... 도대체 1차원 반복문으로 어떻게 푼담.

 

처음에는 set의 합집합을 이용해서 풀어볼까 했다. 그러나 이렇게 되면 중복되는 경우를 잡지 못한다는 단점이 있다.

 

엥 그러면 어떻게 풀지.

 

그래서 다른 사람의 풀이를 보니 map과 나누기로 풀 수 있다는 걸 알 수 있었다.

두 번째 접근

일단 배열을 정렬한다. 정렬을 해주는 이유는 map의 key값보다 항상 크거나 같도록 만들어주기 위함이다.

그리고 각 몸무개를 1.0, 2.0/3.0, 1.0/2.0, 3.0/4.0으로 나눈다. 여기서 나누는 값은 2와 3과 4로 만들 수 있는 분수의 경우의 수이다.

그리고 그렇게 나눈 모든 값을 map과 비교해서 해당 key가 있으면 value를 더해준다. 마지막으로 각 몸무게가 한 번 이상이 나왔으면 1을 더해주고 처음 나온 값이면 0을 더해준다.

코드

java

import java.util.*;


class Solution {
    public long solution(int[] weights) {
        long answer = 0;
        Arrays.sort(weights);
        Map<Double, Integer> map = new HashMap<>();

        for(int i=0; i<weights.length; i++){
            double w1 = weights[i]*1.0;
            double w2 = (weights[i]*2.0)/3.0;
            double w3 = (weights[i]*1.0)/2.0;
            double w4 = (weights[i]*3.0)/4.0;

            if(map.containsKey(w1)){
                answer += map.get(w1);
            }
            if(map.containsKey(w2)){
                answer += map.get(w2);
            }
            if(map.containsKey(w3)){
                answer += map.get(w3);
            }
            if(map.containsKey(w4)){
                answer += map.get(w4);
            }
            
            map.put((weights[i]*1.0), map.getOrDefault((weights[i]*1.0), 0)+1);

        }
        
        return answer;
    }
}