[Java] Lv2 시소 짝꿍

문제

문제 풀이

이론은 아래의 블로그에서 참고하였다.

[Java] 프로그래머스 시소 짝꿍

 

이분 탐색을 이용한 풀이법이다.

4가지 조건을 생각한다.

a == b

a * 2 == b

a * 3 == b * 2

a * 4 == b * 3

4조건을 만족한다면 answer + 1 해준다.

이때 다른 조건을 보지 않도록 a <= b을 만족하게 weights를 정렬한다.

위의 말이 무슨 소리 인고 하니

만약 a, b 두 숫자를 뽑았을 때 a가 더 클 경우

a * 2 == b 등의 조건은 성립할 수 가 없다. ( a가 무조건 더 크다.)

i = 0; j = 0 에서 ++ 해가면서 하나하나 비교한다고 쳤을 때 정렬이 되어 있지 않다면 위의 조건만 보고 정답을 찾을 수가 없다. 위의 조건들은 뽑은 a, b 두 수 중 a가 무조건 작거나 같다는 조건이 필요하다.

이제 이중 for문으로 탐색을 시작한다. 이 때 시간초과를 벗어나기 위해 최대한 시간을 단축해야한다.

그래서 이중 for문의 탐색 조건을 weight[i] * 2 보다 큰 숫자(mid)까지만 진행한다. (weight[i] * 2 보다 큰 값에서부터 -1 해나간다는 소리)

a, b 가 있을 때 a * 2 < b일 경우 b 이후의 값들은 모두 위 4조건을 만족하지 못한다. 일단 a * 2 == b 부터 성립이 안된다.

ex. a * 4 < b * 2이기 때문에 a * 4 =< b * 3

ex2. a * 3 < b * 1.5 이기 때문에 a * 3 < b * 2

마지막으로 중복 처리해주기.

2단계) i == i  - 1 라는 것은 1단계) 에서 나온 answer 수 중에 i == i + 1을 제외한 모든 경우의 수가 같다는 뜻이다.

그렇기 때문에 이전 단계의 정답 - 1 만큼 answer에 더해주기만 하면 끝이다. 

 

자바 코드

import java.util.*;
class Solution {
    private int wLen;
    public long solution(int[] weights) {
        long answer = 0;
        // (A,B)가 있을 때 항상 A <= B를 성립하게 하기위해 정렬한다.
        Arrays.sort(weights);
        wLen = weights.length;
        
        int preValue = 0;
        for(int i = 0; i < wLen - 1; i++){
            // 만약 Weights의 i자리가 이전 i - 1자리와 같다면
            // 이전 단계에서 i = i + 1 자리를 비교했던 +1 값을 제외한 모든 값이 
            // 이전 단계와 answer값이 같기 때문에 이전 단계의 값 - 1 만큼 더해주고
            // 다음 단계로 넘어간다.
            if(i > 0 && weights[i] == weights[i - 1]){
                preValue--;
                answer += preValue;
                continue;
            }
            
            int j = findRignt(weights, weights[i], i + 1);
            preValue = 0;
            // num * 2보다 큰 값부터 i + 1 자리까지 조건을 검사한다.
            // i = j 이거나
            // i * 2 = j
            // i * 3 = j * 2
            // i * 4 = j * 3 인 경우 answer를 + 1
            for(; j > i; j--){
                if(weights[i] == weights[j]){
                    preValue++;
                }else if(weights[i] * 3 == weights[j] * 2){
                    preValue++;
                }else if(weights[i] * 2 == weights[j]){
                    preValue++;
                }else if(weights[i] * 4 == weights[j] * 3){
                    preValue++;
                }
            }
            answer += preValue;
        }
        return answer;
    }
    
    // 이분 탐색 
    // num에서부터 num * 2 인 값을 이분탐색한다.
    // num * 2인 값보다 큰 값을 찾는 이유는 a, b에 대해서 a * 2 < b인 시점에
    // 위의 4조건을 볼 필요도 없어진다. 즉 그 이후 값을 볼 필요가 없다.
    public int findRignt(int[] weights, int num, int i){
        int left = i;
        int right = wLen - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(weights[mid] > num * 2)return mid;
            else left = mid + 1;
        }
        return left;
    }
}