[Programmers] 시소 짝꿍(Python, Java)

문제

요약

시소의 중심으로부터 2, 3, 4 거리에 앉을 수 있다.

시소에서 무게 비율과 거리의 곱이 같은 경우는 몇개인가?

 

문제

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

프로그래머스

---

풀이

Python

풀이1(시간초과)

하나씩 순회하며 확인하는 코드는 시간초과가 발생했다.

값이 몇개씩 있는 경우를 빼서 확인해야 할 것 같다.

def solution(weights):
    answer = 0
    weights.sort()
    
    for i in range(len(weights)-1):
        for j in range(i+1, len(weights)):
            if weights[i] == weights[j]:
                answer += 1
            elif weights[i]/weights[j] in (2/3, 2/4, 3/4):
                answer += 1
            elif weights[j] > weights[i] * 2:
                break
    
    return answer

 

풀이2(정답)

Counter를 이용해서 개수를 확인하고 set로 중복되는 값을 제거했다.

반복문을 두개 쓸 필요 없이 해당 값에 비율을 곱해서 있는지 없는지 확인했다.

같은 숫자가 여러개인 경우는 nC2로 n*(n-1)/2.

from collections import Counter
def solution(weights):
    answer = 0
    counter = Counter(weights)
    weights = set(weights)
    
    for k, v in counter.items():
        if v >= 2:
            answer += v*(v-1)//2
    
    for w in weights:
        if w * (2/3) in weights:
            answer += counter[w] * counter[w*(2/3)]
        if w * (2/4) in weights:
            answer += counter[w] * counter[w*(2/4)]
        if w * (3/4) in weights:
            answer += counter[w] * counter[w*(3/4)]
        
    return answer

 

Java

위의 파이썬 코드를 자바로 그대로 바꾼 코드이다.

사실 이것보다 단순한 자바 풀이가 있지만, 자바 언어도 익힐겸 그대로 바꾸면서 stream, for  반복문 등을 써보았다.

이 문제에서 아주 사소한 것에서 계속 오답이 발생했는데 Long으로 둔 Map의 value값을 Integer로 두면 오답처리가 된다.

이유는 Integer의 범위 때문에. Integer의 표현 범위는 -2,147,483,648 ~ 2,147,483,647이다.

최대 길이만큼 모두 같은 수라고 했을 때, 100,000 * 99,999 / 2 = 4,999,950,000로 범위를 넘어서게 된다. 따라서 Integer가 아닌 Long으로 둬야 한다.

확실히 파이썬 보다 신경써야 할 게 많다.

import java.util.*;

class Solution {
    public Map<Double, Long> Counter(int[] lst) {
        Map<Double, Long> dict = new Hashtable<Double, Long>();
        for (int i: lst) {
            dict.put((i * 1.0), dict.getOrDefault((i * 1.0), (long)0) + 1);
        }
        return dict;
    }
    
    public long solution(int[] weights) {
        long answer = 0;
        Map<Double, Long> counter = Counter(weights);
        
        answer += counter.values().stream()
            .filter(v -> v >= 2)
            .mapToLong(v -> v * (v - 1) / 2)
            .sum();
        
        for (Double k : counter.keySet()) {
            
            if (counter.containsKey(k*2/3)) {
                 answer += counter.get(k) *counter.get(k*2/3);
            }
            if (counter.containsKey(k*2/4)) {
                 answer += counter.get(k) * counter.get(k*2/4);
            }
            if (counter.containsKey(k*3/4)) {
                 answer += counter.get(k) * counter.get(k*3/4);
            } 
        }
        
        return answer;
    }
}