[프로그래머스/Java] 시소 짝꿍 - Level 2

프로그래머스

 

• 문제

놀이터에 시소가 있다. 시소는 중심으로 부터 2, 3, 4m 거리의 지점에 좌석이 하나씩 있다.

 

각 사람마다 무게가 존재하고 거리 X 사람의 무게가 같다면 시소 짝꿍이 될 수 있다.

 

• 입력

int 배열 weights가 주어지며 길이는 2이상 10만 이하이다.

weights[i]는 100이상 1000이하이다.

 

• 풀이

문제를 정확하게 풀어내기 위해서는 완탐으로 10만 X 10만의 시간복잡도가 처음으로 생각날 것이다. 하지만, 10만X10만은 문제를 많이 풀어보면 알겠지만 완탐으로 시간초과가 나오기 아주 좋은 숫자이다. 보통 O(N^2)로 풀어낼 때, N이 10만이상이면 시간을 줄일 생각을 먼저해야한다.

 

그렇다면, 어떻게 시간을 줄일까? 제한 사항을 읽어보며, weights[i]의 숫자가 문제를 풀어낼 수 있는 key임을 알 수 있었다. weights 배열을 한바퀴 돌며, 100에서 1000사이의 값의 개수를 구한 뒤 100~1000사이를 돌면 끝나는 문제였다. 이대로 구현하면 문제는 크게 O(N+900)으로 O(N)만에 문제를 풀어낼 수 있다.

 

• 오답 코드 

class Solution {
    public long solution(int[] weights) {
        long answer = 0;
        int[] arr = new int[1001];
        for(int i = 0; i < weights.length; i++) {
            arr[weights[i]]++;
        }
        
        long[] sameNumber = new long[100001];
        sameNumber[0] = 0;
        sameNumber[1] = 0;
        for(int i = 2; i <= 100000; i++) {
            sameNumber[i] = (sameNumber[i-1]+(i-1));
        }
        
        for(int i = 100; i <= 1000; i++) {
            if(arr[i] == 0) continue;
            
            answer += sameNumber[(int)arr[i]];
            double divideOfTwo = i/2.0;
            double divideOfThree = i/3.0;
            if(divideOfTwo*3 <= 1000) {
                if(isInteger(divideOfTwo*3)) {
                    answer += (arr[i]*arr[(int)(divideOfTwo*3)]);
                }
            }
            if(divideOfTwo*4 <= 1000) {
                if(isInteger(divideOfTwo*4)) {
                    answer += (arr[i]*arr[(int)(divideOfTwo*4)]);
                }
            }
            if(divideOfThree*4 <= 1000) {
                if(isInteger(divideOfThree*4)) {
                    answer += (arr[i]*arr[(int)(divideOfThree*4)]);
                }
            }
        }
        return answer;
    }
    
    public boolean isInteger(double num) {
        return Math.floor(num) == num;
    }
}

풀이대로 구현했지만 3개의 답안이 통과되지 못했다. 약 30분을 고민하며 코드를 살펴본 결과 답을 알 수 있었다. 문제는 아래에 있었다.

int[] arr = new int[1001];

int형 배열로 선언한 것이 무엇이 문제일까? 아래를 보고선 힌트를 얻어보자.

answer += (arr[i]*arr[(int)(divideOfTwo*3)]);

문제가 무엇인지 알 수 있을까? 모르겠다면 조금 더 고민해보자.

 

 

정답은 arr[i]가 5만 arr[(int)(divideOfTwo*3)]가 5만이라고 생각해보자. 곱하면 25억이 나오지만 int형은 21억까지만 표현할 수 있기때문에 쓰레기 값이 나오게된다. 해결방법은 arr배열을 long타입으로 선언하면 된다.

 

• 정답 코드

class Solution {
    public long solution(int[] weights) {
        long answer = 0;
        long[] arr = new long[1001];
        for(int i = 0; i < weights.length; i++) {
            arr[weights[i]]++;
        }
        
        for(int i = 100; i <= 1000; i++) {
            if(arr[i] == 0) continue;
            
            answer += (arr[i]-1)*arr[i]/2;
            double divideByTwo = i/2.0;
            double divideByThree = i/3.0;
            if(divideByTwo*3 <= 1000) {
                if(isInteger(divideByTwo*3)) {
                    answer += (arr[i]*arr[(int)(divideByTwo*3)]);
                }
            }
            if(divideByTwo*4 <= 1000) {
                if(isInteger(divideByTwo*4)) {
                    answer += (arr[i]*arr[(int)(divideByTwo*4)]);
                }
            }
            if(divideByThree*4 <= 1000) {
                if(isInteger(divideByThree*4)) {
                    answer += (arr[i]*arr[(int)(divideByThree*4)]);
                }
            }
        }
        return answer;
    }
    
    public boolean isInteger(double num) {
        return Math.floor(num) == num;
    }
}

 

!TIP
추가로 sameNumber 배열은 같은 수일 때 짝꿍 개수를 얻기 위해 dp형식으로 만들었지만, (n-1)*n/2로 표현할 수 있음을 이후에 알게되어 고쳤다.