프로그래머스 - 시소 짝꿍(Java)

이진 탐색 문제입니다.

비례식과 이진탐색 상한과 하한을 적용하여 해결했습니다.

 

1. 비례식

몸무게의 좌우 균형을 맞추기 위해서는 비율 계산이 필요합니다.

비율 계산, 즉 비례식은 다음과 같습니다.

이는 '내항과 외항의 곱이 같다'라고 나타낼 수 있습니다.

이를 이항을 통해 y를 구하는 하나의 식으로 나타낼 수 있습니다.

예를 들어, 270 과 3 : 4의 비율을 갖는 y의 식은 다음과 같습니다.

식의 결과로 y는 360이 나오게 됩니다.

 

2. 이진탐색 상한 및 하한

이진 탐색은 기본적으로 정렬이 되어있어야 합니다.

 

배열을 탐색 하면서 현재 위치와 다음 위치들을 비교합니다.

현재 위치가 맨 위의 식에서 x가 되고, 비율을 통해 y을 구합니다.

int y = ((x * rate[0]) / rate[1]);

 

비율은 1:1, 2:3, 2:4, 3:4만이 존재합니다.

private static final int[][] rates = {{1, 1}, {3, 2}, {4, 2}, {4, 3}};

(외항, 내항 연산을 순서대로 하기 위해 좌, 우 위치를 반대로 했습니다.)

 

여기서 중요합니다.

비율 계산을 통해 구해진 y의 값이 다음 위치에 존재하는지 구하면 됩니다.

해당 비율의 값 y를 가진 것이 있을 때는 짝이 존재 하는 것이고,

없으면 짝이 존재하지 않는 것입니다.

 

일반적으로 반복을 통해 구할 수는 있지만,

주어진 N의 값이 100,000 이기 때문에 이진 탐색을 통하면 더 빠른 속도로 구할 수 있습니다.

int upper = upperBound(y, weights, i + 1, weights.length);

현재 위치가 i 입니다.

i+1 부터 배열 끝까지 y의 값을 이진 탐색을 통해 존재하는지 확인합니다.

(0 부터 i-1 번째 까지는 짝꿍 매칭을 이미 완료한 상태입니다.)

 

이진 탐색의 상한과 하한을 구하는 이유가 무엇일까요?

그것은 바로 배열에 중복된 값이 들어갈 수 있기 때문입니다.

상한과 하한의 차이를 구하면 중복된 값이 몇 개 있는지 확인할 수 있습니다.

물론, 정렬을 했기 때문에 다음 위치부터 반복을 해 중복 요소의 개수를 구할 수 있긴 합니다만 속도가 느립니다.

 

[구현 코드]

import java.util.Arrays;

class Solution {

    private static final int[][] rates = {{1, 1}, {3, 2}, {4, 2}, {4, 3}};

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

        // 정렬
        Arrays.sort(weights);

        // 비율 만큼 반복
        for (int[] rate : rates) {
            for (int i = 0; i < weights.length; i++) {
                int x = weights[i];

                // 비율 계산을 통해 y를 구함
                if (x * rate[0] % rate[1] != 0) continue;
                int y = ((x * rate[0]) / rate[1]);

                // y의 값이 i+1 부터 존재하는지 확인함
                int upper = upperBound(y, weights, i + 1, weights.length);
                
                // 하한 탐색은 상한 탐색의 위치 이하이므로 탐색 마지막 위치를 upper 해도 됨
                int lower = lowerBound(y, weights, i + 1, upper);

                // 상한과 하한의 값을 빼서 중복된 값이 몇 개 인지 정답에 더함
                // 만약 y의 값이 범위 내에 존재하지 않으면,
                // 상한과 하한 둘 다 i+1의 위치를 반환하기 때문에 둘의 차이는 0이 될 것임
                answer += (upper - lower);
            }
        }

        return answer;
    }

    // 상한
    private static int upperBound(int findWeight, int[] weights, int left, int right) {
        while (left < right) {
            int mid = (left + right) / 2;

            if (findWeight < weights[mid]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    // 하한
    private static int lowerBound(int findWeight, int[] weights, int left, int right) {
        while (left < right) {
            int mid = (left + right) / 2;

            if (findWeight <= weights[mid]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}