[프로그래머스] 시소 짝꿍 / 자바(Java)

문제

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

프로그래머스

 

---

해설

weights의 길이가 딱 봐도 길어 일일히 비교한다면 약 100억번의 연산, O(n^2)이 필요해 시간복잡도를 고려해야하는 문제입니다.

일일히 비교하지 않고 쉽게 있던 값을 검색하는 방식으로 특정 무게를 키로 가지고 해당 무게를 가진 사람의 수를 값으로 가진 Map을 사용해야한다고 생각되었습니다.

 

또한 우리가 확인해야할 좌석은 3가지로 총 비교 횟수는 6가지에 추가로 같은 무게인 경우까지 7가지이므로 이를 줄이기위해 정렬을 통해 새로 넣는 무게는 이전과 비교해 더 작을수 없음을 이용하여 같은 무게인경우, 2:3비율, 2:4비율, 3:4비율 4가지만 확인하도록 합니다.

 

배열 weights를 따라가며 이번 무게의 비율로 연산되는 값들을 계산해 각각 map에 있던 무게들과 계산해 일치하는 경우는 해당 무게를 가진 사람들과 시소 짝꿍이 되었다 보고 answer에 값을 추가해줍니다.

이후 해당 무게를 map에서 값을 1만큼 추가해 새로 등록하는 형식으로 하여 총 O(NlogN)으로 더 빠르게 통과가능합니다.

주의점

• 2 ≤ weights의 길이 ≤ 100,000
• weights의 각 요소는 100~1000

---

코드

import java.util.*;
class Solution {
    public long solution(int[] weights) {
        long answer = 0;
        Map<Double, Integer> m = new HashMap<>();
        Double[] checkN = new Double[4];
        Arrays.sort(weights);
        for(int weight : weights){
            checkN[0] = weight*1.0;
            checkN[1] = (weight*2.0)/3.0;
            checkN[2] = (weight*2.0)/4.0;
            checkN[3] = (weight*3.0)/4.0;
            
            for(int i=0;i<4;i++){
                if(m.containsKey(checkN[i])) answer += m.get(checkN[i]);
            }
            m.put(checkN[0], m.getOrDefault(checkN[0],0)+1);
        }
        return answer;
    }
}

 

추가코드

weights의 크기 범위가 정수이며 최대 1000으로 한정되어 있다는 것에서 찾는 방안으로 Map을 통한 검색이 아닌 배열에 해당 인덱스를 키로 삼고, 배열의 값을 해당 무게인 사람의 수로 하는 방식이 있었습니다. 이또한 참신하며 O(N)으로 빠르고 쉽게 풀 수 있는 방식이라 생각해 추가코드에 첨부합니다.

class Solution {
    public long solution(int[] weights) {
        long answer = 0;
        long[] arr = new long[1001];

        for(int i = 0; i < weights.length; i++){
            arr[weights[i]]++;    
        }

        for(int i = 100; i < 1001; i++){
            if(arr[i] == 0) continue;
            answer += (arr[i] * (arr[i] - 1)) / 2;

            if((4 * i) / 3 > 1000) continue;
            if(i % 3 == 0){
                answer += arr[i] * arr[(4 * i) / 3];
            }

            if((3 * i) / 2 > 1000) continue;
            if(i % 2 == 0){
                answer += arr[i] * arr[(3 * i) / 2];
            }

            if(2 * i >1000) continue;
            answer += arr[i] * arr[2 * i];
        }

        return answer;
    }
}