시소 짝꿍

문제 : 

어느 공원 놀이터에는 시소가 하나 설치되어 있습니다. 이 시소는 중심으로부터 2(m), 3(m), 4(m) 거리의 지점에 좌석이 하나씩 있습니다.
이 시소를 두 명이 마주 보고 탄다고 할 때, 시소가 평형인 상태에서 각각에 의해 시소에 걸리는 토크의 크기가 서로 상쇄되어 완전한 균형을 이룰 수 있다면 그 두 사람을 시소 짝꿍이라고 합니다. 즉, 탑승한 사람의 무게와 시소 축과 좌석 간의 거리의 곱이 양쪽 다 같다면 시소 짝꿍이라고 할 수 있습니다.
사람들의 몸무게 목록 weights이 주어질 때, 시소 짝꿍이 몇 쌍 존재하는지 구하여 return 하도록 solution 함수를 완성해주세요.

import java.util.*;
class Solution {
    public long solution(int[] weights) {
        long answer = 0;
        Arrays.sort(weights);
        int tmpCount=0;
        for(int i=0; i<weights.length-1; i++){
            if(i!=0 && weights[i]==weights[i-1]){
                tmpCount-=1;
                answer+=tmpCount;
                continue;
            } else {
                tmpCount=0;
            }
            for(int j=i+1; j<weights.length; j++){
                if(weights[i]==weights[j]
                   || (weights[i]*3)==(weights[j]*2)
                   || (weights[i]*4)==(weights[j]*2)
                   || (weights[i]*4)==(weights[j]*3)
                  ){
                    tmpCount++;
                } else if(weights[i]*4<weights[j]*2){
                    break;
                }
            }
            answer+=tmpCount;
        }
        return answer;
    }
}

단순 2중 for문으로 전체를 돌리면 당연하게도? 시간 초과가 발생한다.

 

해결 1)

이를 해결하기 위해 비교값 중 작은 값의 최댓값(4m일 때)이 큰 값의 최솟값(2m일 때)보다 작다면,

오름차순 정렬된 배열에서 이후의 값은 더 이상 비교할 필요가 없기 때문에 다음 값으로 넘어가도록 해결했다.

 

ex)

int[] a = [2, 3, 4, 5, 6, 8, 10, 16, 20] 과 같이 되어 있다고 할 때, a[0]인 2를 기준으로 가장 큰 조건인 8(4m인 상황)이 될 수 있는 수 중 최댓값인 4(2m일때 8이므로)를 초과한 숫자에 대해서는 더 이상 비교할 필요가 없다. 그 뒤의 값은 당연하게도 전부 성립이 불가능하기 때문

 

 

그래도 일부 상황에서는 시간초과가 여전히 발생했다.

 

 

해결 2)

중복이 가능한 배열이기 때문에, 중복의 경우 앞의 상황보다 1만큼 작은 경우의 수가 발생하는 것을 반복문 대신 tmpCount 도입하여 해결

 

ex)

int[] a = [2, 2, 2, 2, 2, 4, 5] 와 같은 배열이라고 했을 때, 제일 첫번째에 있는 2는 총 5개의 짝꿍이 생긴다(a[1], a[2], a[3], a[4], a[5])

하지만 그 다음에 있는 2는 a[0]을 제외한 총 4개의 짝이 생겨야 한다.( a[2], a[3], a[4], a[5] )

즉, 정렬된 배열일 때 이전의 값과 같은 값이라면 이전의 값보다 하나가 적은 수의 짝꿍이 생길 것이다.

그래서 반복문 한 번이 실행될 때마다 해당 값의 짝꿍 수를 tmpCount에 저장해두고, 다음 반복 진입 시 만약 이전의 값과 같은 값이라면 tmpCount에 -1을 해서 답에 더해준 후 반복문을 진행하지 않고 넘어가도록 작성