[프로그래머스] Lv.2 시소 짝꿍 (Java)

문제

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

프로그래머스

 

풀이

이진탐색 이용

 

우선 몸무게를 오름차순으로 정렬한다.

이제 몸무게가 a,b (a<=b)인 두 사람이 있을 때 둘이 시소 짝꿍이 될 수 있는 경우의 수는 다음 네 가지이다.

1. 2a = 2b (즉 몸무게가 같은 경우, a=b)
   • 문제 조건에 의해 시소의 1(m)거리 지점에 앉을 수 없으므로 2a = 2b라고 나타낸 것이다.
2. 2a = b
3. 3a = 2b
4. 4a = 3b

weights 배열을 오름차순으로 정렬한 뒤 weights[i]를 하나씩 방문하고, i보다 큰 j에 대해서 weights[i]와 시소 짝꿍이 되는 경우의 수를 만족하는 weights[j]를 찾으면 answer를 1 증가시켜주면 된다.

그런데 이 때 j의 인덱스를 배열의 끝으로 잡으면 시간복잡도가 O(N^2)가 되고 시간초과가 뜬다.

그래서 '가능성이 있는' 인덱스까지 j의 범위를 잡아주어서 시간을 줄여주어야 한다. 그렇다면 '가능성이 있는가'를 어떻게 판단해야 좋을까?

경우의 수를 다시 보자.

 

 `a=b` a와 b의 값이 다른 경우, 가능성 zero 

a와 b의 값이 같은 경우는 특수한 경우이므로 일단 제외하자.

 

a와 b 값이 다르고 b는 a보다 크다. 이 때, 

`2a=b` 2a<b인 경우, 가능성 zero

`3a=2b` (3/2)*(a)<b인 경우, 가능성 zero

`4a=3b` (4/3)*(a)<b인 경우, 가능성 zero

a와 b의 값이 다른 경우 b의 최소 필요조건은 2a 보다는 커야 한다는 것이다.

2a<b인 경우, 뒤의 나머지 조건들도 만족할 가능성이 없다.

2번에서 4번으로 갈수록 조건의 폭이 좁아지고 있다는 것을 이해해야 한다.
2a<b이면 항상 3a<2b인가?를 증명해보면 된다.
2a<b의 양변에 1.5를 곱해보자.
3a<1.5b는 항상 성립한다. 
1.5b는 항상 2b보다 작다.
그러므로 3a는 항상 2b보다 작다.

2a<b이면 항상 4a<3b인가?도 증명해보자.
2a<b의 양변에 2를 곱해보자.
4a<2b는 항상 성립한다.
역시 2b는 항상 3b보다 작으므로 4a는 항상 3b보다 작다.

그래도 이해가 안 간다면 아래 사진을 참고하자.

 

 

자 그럼 2*weight[i]보다 큰 weight[j]를 가지는 j 중 가장 작은 j를 찾으면 된다. j보다 큰 인덱스에 대해선 가능성이 zero이므로 확인할 필요가 없다. 이 j를 찾는 데에 이진 탐색을 사용한다.

 

import java.util.*;

class Solution {
    public long solution(int[] weights) {
    long answer = 0;
    Arrays.sort(weights);
    for(int i=0; i<weights.length-1; i++) {
      // 몸무게가 weights[i] 보다는 크고, weights[i]*2보다는 작거나 같은 weight까지 조건 확인
      int lastIdx = searchEndIdx(weights, 2*weights[i], i);
      for(int j=i+1;j<=lastIdx;j++) {
        if(weights[i]==weights[j] || weights[i]*2==weights[j] || weights[i]*3==weights[j]*2 || weights[i]*4==weights[j]*3) {
          answer++;
        }
      }
    }
    return answer;
  } 

  public int searchEndIdx(int[] arr, int targetValue, int curIdx) {
    // curIdx+1 ~ 배열 마지막 원소중에서
    // targetValue보다 큰 값을 가지는 최초 원소 return 
    int start = curIdx;
    int end = arr.length-1;
    int mid;
    while(start<end) {
      mid = (start+end)/2;
      if(arr[mid]<=targetValue) {
        start = mid+1;
      } else {
        end = mid;
      }
    }
    return start;
  }
}​

 

 

그런데 위 코드는 시간 초과가 뜬다

미워 ㅠ

 

+ 중복 케이스 처리

이 블로그(https://0713k.tistory.com/40)를 통해 중복 케이스를 처리하면 된다는 사실을 알고 중복 처리를 해주었더니 바로 통과했다.

• weights배열에서 현재 인덱스 `i`의 원소가 이전 인덱스 `i-1` 원소와 몸무게가 같을 때
• `i-1`이 가질 수 있는 시소 짝꿍의 수에 -1을 해준 값이 `i`가 가질 수 있는 시소 짝꿍의 수이다.
  • 여기서 -1은 `i-1`과 `i`가 짝꿍이 되는 경우의 수를 의미한다. 이 경우는 i-1번째에서 이미 포함되었으므로 1을 빼주어야 한다.

import java.util.*;

class Solution {
    public long solution(int[] weights) {
    long answer = 0;
    Arrays.sort(weights);
    int prevCnt = 0;
    for(int i=0; i<weights.length-1; i++) {
      if(i>0 && weights[i]==weights[i-1]) {
          answer+=(--prevCnt);
          continue;
      }
      // 몸무게가 weights[i]*2보다 작거나 같은 weight까지 확인
      int lastIdx = searchEndIdx(weights, 2*weights[i], i);
      prevCnt=0;
      for(int j=i+1;j<=lastIdx;j++) {
        if(weights[i]==weights[j] || weights[i]*2==weights[j] || weights[i]*3==weights[j]*2 || weights[i]*4==weights[j]*3) {
          prevCnt++;
        }
      }
      answer+=prevCnt;
    }
    return answer;
  } 

  public int searchEndIdx(int[] arr, int targetValue, int curIdx) {
    // curIdx+1 ~ 배열 마지막 원소중에서
    // targetValue보다 큰 값을 가지는 최초 원소 return 
    int start = curIdx;
    int end = arr.length-1;
    int mid;
    while(start<end) {
      mid = (start+end)/2;
      if(arr[mid]<=targetValue) {
        start = mid+1;
      } else {
        end = mid; // 조건을 만족한다고 판단, (mid-1)가 아닌 mid로 대입
      }
    }
    return start;
  }
}