[프로그래머스] 시소 짝궁(Java)

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

프로그래머스

---

문제 풀이

시소 거리에 따라 rates 배열을 만들었다.

그리고 for문을 돌며 체크.. 하지만 아래 코드는 타임아웃 우려가 있어 사용하지 않는게 좋다.

import java.util.*;

class Solution {
    public long solution(int[] weights) {
        Map<Integer, Integer> answerMap = new HashMap<>();
        int[][] rates = {{1, 1}, {3, 2}, {4, 2}, {4, 3}};
        
        for(int i=0; i<weights.length; i++) {
            int left = weights[i]; // 왼쪽에 앉은 사람 무게
            
            for(int l=0; l<weights.length; l++) {
                int right = weights[l]; // 오른쪽에 앉은 사람 무게
                
                if(i == l) {
                    break;
                }
                
                for(int j=0; j<rates.length; j++) {
                    int sum1 = left * rates[j][0];
                    int sum2 = right * rates[j][1];
                    
                    if(sum1 == sum2) {
                        answerMap.put(sum1, sum1);
                    }
                }
            }
        }
        return answerMap.size();
    }
}

 

아래는 수정한 소스코드이다.

1. 먼저, weights 배열을 오름차순 정렬 해준다. -> 같은 무게를 빨리 찾기 위해

2. 같은 무게를 가진 경우의 수를 찾아준다. sameNum 변수에 담고 전체 answer 에서 빼준다. -> 후에 같은 경우의 수를 같이 계산

3. 균형을 이루는 경우의 수를 찾아준다.

 

import java.util.*;

class Solution {
    public long solution(int[] weights) {
        long answer = 0;
        Arrays.sort(weights); // 오름차순 정렬
    
        int sameNum = 0;
        for(int i=0; i<weights.length-1; i++) {
            
            if(i>0) {
                if(weights[i-1] == weights[i]) {
                    sameNum--;
                    answer += sameNum;
                    continue;
                }
            }
             
            sameNum = 0;
            
            for(int j=i+1; j<weights.length; j++) {
                int left = weights[i];
                int right = weights[j];
                
                if(left == right ||
                   left * 3 == right * 2 ||
                   left * 2 == right * 1 ||
                   left * 4 == right * 3) {
                    answer++;
                }
            }
            answer += sameNum;
        }
        
        return answer;
    }
}