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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/152996?language=java 

프로그래머스

주어진 조건의 짝궁이 몇 개인지 리턴하는 문제

 

풀이

이분 탐색으로 풀었다. 

처음에 중복 없이 구현했는데 테스트 케이스 15가 통과가 안됐다.

분명히 이분탐색 맞는데..?

오랜 시간 고뇌 끝에 중복 케이스를 손보니 통과됐고, 속도도 매우 빨라졌다. 

시원시원하다

로직은 다음과 같다. 

1. 우선 주어진 배열 w[] 을 정렬한다. 
2. 2중  for를 도는데 안쪽 j 의 최대 범위를 이분 탐색으로 찾는다.
3. 숫자 w[i], w[j] 가 문제의 조건을 맞으면 카운팅.
4. w[i] == w[i-1] 중복 처리를 해준다. 
5. 정답을 리턴한다. 

 

문제부터 다시 보겠다. 

문제에서 요구하는 것은 주어진 숫자 배열  weigts[] 에서 두 개의 숫자(a,b)를 뽑은 다음, 그 숫자가 다음 조건을 만족하냐 보는 것이다. 

정답 카운팅 조건(숫자 a, 숫자 b 를 비교할때) : 다음 조건 중 한개라도 만족하면 된다. 

• [조건1] a  == b
• [조건2] a x 2 == b x 1 (이것은 a x 4 == b x 2 에서 양쪽에 2 를 나눈 것이다) 
• [조건3] a x 3 == b x 2
• [조건4] a x 4 == b x 3

어? 다른 조건들은 왜 안봐! 

자자. 우선 이진 탐색을 위해 정렬을 할 것이어서 a, b를 뽑을때 a <= b 가 무조건 참이 된다. 

그럼으로 a x w1  > b x w2  가 되는 조건들은 신경 안 쓸것이다. 

• a x 3 == b x 3 , a x 4 == b x 4 조건은 안 본다. 이미 조건 1에 만족한다

그 다음 2중 for를 작성한다. 

어? O(N^2)인데 TLE 뜰텐데? 

이때 안쪽의 for를 N만큼 탐색 하지 않고,  이분탐색으로 범위를 찾은 다음 탐색한다. 이때 범위의 조건은 바깥 for 변수 i 의 weights[i] x 2 보다 큰 숫자 이면 ok. 

            /*이분 탐색으로 j 의 최대 범위를 찾는다.*/
            int j = findRignt(w,w[i], i+1);
            for(; j > i ;j --){
            //조건 하나라도 걸리면 증가!
                if(w[i] == w[j] ||w[i] * 2== w[j] 
                   || w[i] * 3 == w[j] * 2 || w[i] * 4 == w[j] * 3){
                    ans++;
                }
            }

findRight 코드는 다음과 같다.

현재 num 에서 num x 2 보다 큰 숫자를 이분 탐색한다.

    public int findRignt(int[]w, int num, int i){
        int left = i;
        int right = len-1;
        while(left < right){
            int mid = left +(right-left)/2;
            if(w[mid] > num*2)return mid;
            else left = mid+1;
        }
        return left;
    }

 

마지막으로 중복 처리 해준다.

• prev 변수를 이용해서 현재 i 번째 값을 저장하고 w[i] == w[i-1] 이면 answer += prev-1 을 해준다.
• 경우의 수가 1만 줄어드니깐 prev-1

 

참고

이분 탐색에서 종료 조건을 num x 2 로 한 이유는 

숫자(a,b)를 뽑는다.  문제의 조건에서 조건 1 을 제외하고 a, b가 있는데 , 이때 a * 2 < b 이면 b 의 오른쪽에 위치한 것들도 다 a * 2 보다 크다. 그럼 그 부분은 탐색을 하면 안된다. 왜? 나머지 조건을 검사 해 봐도 a x w1 한것보다 크기 떄문이다. 

 

조합이나, 단순히 break를 포함한 2중 for문을 해본 결과 TLE 가 뜬다. 

딕셔너리 , 해시맵을 사용한 풀이법도 좋지만, 이분 탐색도 실전에서 떠올리기 쉽다.

코드

자바

import java.util.*;

class Solution {
    int len;
    public long solution(int[] w) {
        long answer = 0;
        len = w.length;
        Arrays.sort(w);
        int prev  =0 ;
        for(int i =0 ;i <len-1;i++){
            if(i > 0 && w[i] == w[i-1]){
                prev--;
                answer+=prev;
                continue;
            }
            int j = findRignt(w,w[i], i+1);
            prev = 0;
            for(; j > i ;j --){
                if(w[i] == w[j] ||w[i] * 2== w[j] 
                   || w[i] * 3 == w[j] * 2 || w[i] * 4 == w[j] * 3){
                    prev++;
                }
            }
            answer+=prev;
        }
        return answer;
    }
    public int findRignt(int[]w, int num, int i){
        int left = i;
        int right = len-1;
        while(left < right){
            int mid = left +(right-left)/2;
            if(w[mid] > num*2)return mid;
            else left = mid+1;
        }
        return left;
    }
}