[JAVA] [기타] Pro 시소 짝꿍

문제

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

프로그래머스

코드

import java.util.*;

class Solution {
    public long solution(int[] weights) {
        long answer = 0;
        
        Arrays.sort(weights);
        
        int cnt=0;
        for (int i=0; i<weights.length-1; i++){
            // 이전 숫자와 같다면, 이전 숫자의 cnt 활용
            if(i>0 && weights[i-1]==weights[i]){
                cnt-=1;
                answer+=cnt;
                continue;
            }
            cnt=0;
            for (int j=i+1; j<weights.length; j++){
                // j번째 값이 i번째 값 2배한 것보다 더 크다면 더 계산할 필요없으므로 break
                // 오름차순 정렬을 하면 weigths[i] < weight[j] 이므로 9가지 케이스 다 비교할 필요없이 4가지만 비교해도 된다.
                if(weights[i]*2<weights[j]) break;
                else if(weights[i]==weights[j]) cnt++;
                else if(weights[i]*3 == weights[j]*2) cnt++;
                else if(weights[i]*4 == weights[j]*2) cnt++;
                else if(weights[i]*4 == weights[j]*3) cnt++;
            }
            answer+=cnt;
        }
        return answer;
    }
}

import java.util.*;

class Solution {
    
    static int[][] rates = {{1,1}, {4,3}, {4,2}, {3,2}};
    
    public int upper(int target, int start, int end, int[] arr) {
        
        int left = start;
        // 다른 부분
        int right = end;
        int mid = (left + right)/2;
        while (left < right) {
            mid = (left + right)/2;
            // 다른 부분
            if (target < arr[mid]) {
            	// 다른 부분
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        // 다른 부분
        return left;
    }
    
    public int lower(int target, int start, int end, int[] arr) {
        
        int left = start;
        int right = end;
        int mid = (left + right)/2;
        while (left < right) {
            mid = (left + right)/2;
            if (target <= arr[mid]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    
    public long solution(int[] weights) {
        long answer = 0;
        Arrays.sort(weights); // *오름 차순 정렬
        
        for (int[] rate : rates) {
            for (int i = 0; i < weights.length; i++) {
                
                int nowX = weights[i];
                
                // nowX에 해당하는 y값이 배열에 존재하는 지 체크
                // 아예 y가 정수로 안나오면 패스
                if ((nowX * rate[0] % rate[1]) != 0) continue;
                int findY = nowX * rate[0] / rate[1];
                
                int upperBound = upper(findY, i+1, weights.length, weights);
                int lowerBound = lower(findY, i+1, upperBound, weights);
                
                int tmp = upperBound - lowerBound;
                answer += tmp;
            }
        }
        return answer;
    }
}

https://jackpot53.tistory.com/33