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

문제

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

프로그래머스

 

풀이

이중 for문을 이용하게 된다면 최대 100,000 * 100,000 = 10,000,000,000 번 돌아가서 시간 초과가 발생한다.

따라서 for문 하나만 이용하여 문제를 풀어야 한다.

각 값에 대해 이전에 같은 값이 있었는지 확인하면서 문제를 풀면 된다. 즉, 배열을 이용하여 index를 weight*2,3,4 로 두고 배열 index의 값에 대해 같은 index가 나오면 그 배열 요소의 값이 같은 무게의 개수가 된다. 

 

근데 [1, 1, 1, 1, 1] 과 같은 경우도 있다.

이럴 경우에는 1*2, 1*3, 1*4 모두 같은 값이기 때문에 원하는 값이 안나오게 된다. 

따라서 배열 하나 더 만들어서 기존의 weights 배열의 값을 index로 두는 배열로 만든다.

그리고  weights 요소에 대해 count 한 값이 배열의 요소가 된다.

아무튼 위와 같은 경우에는 기존의 무게 개수에 weight를 count 한 값 * 3을 빼주고 weight를 count한 값을  더해준다.

 

코드

class Solution {
    public long solution(int[] weights) {
        long answer = 0;
        
        int arr [] = new int [4001];
        
        arr[weights[0]*2] = 1;
        arr[weights[0]*3] = 1;
        arr[weights[0]*4] = 1;
        
        int exist [] = new int [100001];
        exist[weights[0]] = 1;
        
        for(int i=1;i<weights.length;i++){           
            for(int j=2;j<=4;j++){
                if(arr[weights[i]*j] > 0 ){
                    answer += arr[weights[i]*j];
                    // System.out.println(weights[i]);
                }
                arr[weights[i]*j] += 1;
            }
            if(exist[weights[i]] >= 1){
                answer = answer - (exist[weights[i]]*3) ;
                answer += exist[weights[i]];
            }
            exist[weights[i]] += 1;
        }
            
       
        return answer;
    }
    
}