프로그래머스 코딩테스트 문제 - [Lv.2] 시소 짝꿍 (Java)

문제 출처 - 링크

알고리즘 분류

• 구현
• 해시

📋 문제 요약 설명

• 시소는 중심으로부터 2(m), 3(m), 4(m) 거리의 지점에 좌석이 하나씩 있다.

• 세 거리중 한 거리를 선택하여 한 명씩 양쪽에 앉는다.

• 몸무게들 중에서 시소가 평형이되는 짝궁이 몇 쌍이 존재하는지 찾아라

💡 알고리즘 설계 / 접근 방법

1. 주어진 거리를 활용해서 시소가 평형이 될 수 있는 몸무게 비율을 변수에 저장한다.

   • (몸무게 A x 거리 = 몸무게 B x 거리) 되어야 시소가 평행이 된다.

2. 몸무게마다 주어진 비율들을 모두 확인하면서 짝꿍 몸무게를 찾는다.

   • 주어진 비율과 몸무게를 계산식에 넣어서 평행이 되는 몸무게(target)을 구한다.

   • 이전에 등장했던 몸무게 중 target이 있다면 이전에 몇 번 등장했는지 찾아서
     그 횟수만큼 쌍이 만들어질 수 있으므로, 그 값을 answer에 누적한다.

   • map에 현재 몸무게가 등장한 횟수를 1 증가한다.

➕ 보완하기 / 성능 비교

• 문제에서 주어진 시소의 거리를 활용해 가능한 몸무게 비율을 변수에 저장해서 계산에 사용하는 아이디어를 활용해야 한다.

✅ 풀이

시간 복잡도 → O(N)

1. 외부 for문 : O(n)
2. 내부 for문 : 7번
3. 정수 연산 및 map 조회, 삽입 : 전부 O(1)

최종 시간 복잡도 : O(n × 7 × O(1)) = O(n)

import java.util.*;

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

        // 등장한 몸무게별 개수를 저장할 Map
        Map<Integer, Long> map = new HashMap<>();

        // 가능한 비율들 (분자, 분모)
        int[][] ratios = {
            {1, 1}, {2, 3}, {3, 2},
            {1, 2}, {2, 1}, {3, 4}, {4, 3}
        };

        for (int weight : weights) {
            // 이전에 등장했던 몸무게 중에서 짝꿍이 될 수 있는 것들을 찾음
            for (int[] ratio : ratios) {
                int numerator = ratio[0];
                int denominator = ratio[1];

                // 정수형 분수(비율)을 곱해 부동소수점 오차를 방지함 -> 나머지가 0인지를 통해 졍수인지 확인함
                // weight * numerator / denominator이 정수인지 확인
                if ((weight * numerator) % denominator != 0) continue;

                // weight × 거리1 == target × 거리2
                // target : 현재 몸무게로 만들 수 있는 균형 짝꿍 몸무게
                int target = (weight * numerator) / denominator;
                
                // weight가 짝꿍이 되려면 이미 등장한 몸무게 중 target이 있어야 함
                answer += map.getOrDefault(target, 0L);
            }

            // 현재 몸무게 등장 수 저장
            map.put(weight, map.getOrDefault(weight, 0L) + 1);
        }

        return answer;
    }
}