프로그래머스_시소짝꿍_Day10

 

알고리즘 챌린지 10일 차이다. 시작할 때는 조금 자신이 없었지만 어느덧 열흘 가까이하다 보니 자신감이 생기고 더 잘할 수 있을 것 같은 느낌이 샘솟는다. 

오늘은 프로그래머스 level2에 분류된 시소짝꿍 문제를 가져왔다. 조건을 보자마자 완전 탐색(O(n^2))은 어려울 것이라는 생각이 들었을 것이다. 
그렇다면 한 번의 반복(O(n))으로 시간 복잡도를 최적화하는 방법을 찾아보아야 한다. 

간단하게 생각해보면 각 무게마다 1:1, 1:2, 2:3, 3:4 비율의 무게를 가진 사람이 몇 명 있는지 체크해보아야 한다. 

경우의 수를 살펴보기 전에 문제에서는 자세하게 언급하지 않았지만 순서쌍이라고 했다. 그 말인 즉, 순서쌍에 포함되는 사람의 종류는 구분이 필요하지만 같은 사람끼리는 순서를 고려할 필요가 없다. 
간단하게 예시를 들어보자면, 5명의 사람이 있다고 해보자. 
A, B, C, D, E의 몸무게가 각각 100, 100, 100, 150, 150이라고 한다. 
이때, 1:1비율을 가지는 (A, B)와 (B, A)는 같은 순서쌍이므로 중복을 제거해 한 번만 체크하면 된다. 
같은 몸무게를 가지는 사람의 수를 w라고 한다면 wC2 = w!/((w-2)!*2!) = w(w-1)/2를 구하면 된다는 것이다. 

다음으로 1:2 비율을 가지는 순서쌍을 살펴보자. 물론 위와 마찬가지로 (A, D)와 (D, A)는 같은 순서쌍이다. 
하지만 (A, E)와 (A, D)는 다른 순서쌍이다. 문자로 보니 다른 것이 명확히 보이기 때문에 이해가 쉽지만 
문제에서 주어진 값으로 표현하면, (100,150)과 (100,150)이 다른 순서쌍이 된다는 뜻이다. 
이 경우 두 값의 곱을 구해야 한다.

2:3, 3:4비율을 가지는 경우는 1:2와 마찬가지다. 이 점을 까먹지 말고 보다 보면 자료구조만을 이용하여 간단하게 풀이할 수 있는 문제다. 

자바와 파이썬에서 사용하는 자료구조가 다르기 때문에 오늘은 소스코드를 먼저 보고 설명하도록 하겠다. 

Java

import java.util.*;
class Solution {
    public long solution(int[] weights) {
        Arrays.sort(weights);
        Map<Double, Integer> map = new HashMap<>();
        long answer = 0;
        for (int i : weights) {
            double a = i * 1.0;
            double b = (i * 1.0) / 2.0;
            double c = (i * 2.0) / 3.0;
            double d = (i * 3.0) / 4.0;
            if(map.containsKey(a)) answer += map.get(a);
            if(map.containsKey(b)) answer += map.get(b);
            if(map.containsKey(c)) answer += map.get(c);
            if(map.containsKey(d)) answer += map.get(d);
            map.put(i*1.0, map.getOrDefault(i*1.0, 0) + 1);
        }
        return answer;
    }
}

 

순열의 경우 개수가 몇 개 있든 간에 2개의 쌍만 뽑는다고 하면 위와 같은 공식으로 일반화할 수 있다. 여기서 간단한 규칙을 찾을 수 있는데, 
2C2 = 1, 3C2 = 1+2, 4C2 = 1+2+3, 5C2=1+2+3+4,... , nC2 = 1+2+3+...+n-1이다.

위와 같은 규칙을 설명해 주는 이유는 1:1인 경우 map을 사용하여 순서쌍을 구할 때 같은 규칙이 보이기 때문이다. 

먼저 배열을 오름차순으로 정렬한 후에 각 요소를 한 번씩 순회하면서 조건에 만족하는 값이 있는지 체크하고 해당 값을 맵에 카운팅 하면서 넣는다. 
이 말은 즉, 반복을 통해 순회되는 몸무게 값이 map의 key값보다 작을 수 없다.(무조건 크거나 같다.) 이 점을 기억하면서 각 경우의 수를 체크해 보자. 

 

1:1의 비율인 경우 

가장 처음 예시를 그대로 사용하여 [100, 100, 100, 150, 150]의 정렬된 결과가 있다고 해보자. 
가장 처음 순회되는 100은 조건에 만족할리가 없으니 그냥 map에 put 된다. 
두 번째로 순회되는 100은 같은 값이 있기 때문에 기존값(1)+1을 하여 map에 put 한다. 
세 번째로 순회되는 100은 같은 값이 있기 때문에 기존값(2)+1을 하여 map에 put 한다. 

여기까지만 봐도 결론적으로 3C2를 구한 것인데, map에 put 하는 순서만 뒤로 미루어 1+2의 결과를 만들 수 있다. 
약간의 수학적인 배경지식으로 접근한 방법이라 이해가 어려울 수도 있지만,, 중복되는 수가 더 늘어난다고 하여도 같은 규칙으로 작용한다. 

 

그 외 비율인 경우 

위에서 설명했듯이 순회되는 값 i는 map의 key값보다 크거나 같다. 그렇기 때문에 현재 값보다 값이 작아지도록 비율을 곱하여 찾는 것이다. 혹시라도 현재 값보다 작은 비율의 값은 카운트했지만 현재 값이 작은 값에 해당하는 경우는 뒤에서 큰 값이 나오는 경우 카운트될 것이기 때문에 고려하지 않아도 된다. 
예를 들어 100, 200, 400의 무게가 있다고 가정하자. 
200을 순회하는 경우 1:2의 비율은 사실 100과 200 두 개가 있고 이 둘은 엄연히 다른 순서쌍이지만, 현재 반복단계에서는 200보다 작은 100만 찾는다.
어차피 뒤이어 400을 순회할 때, 200을 카운트할 수 있기 때문이다. 

 

다음으로는 파이썬 코드를 보자

Python

from collections import Counter

def solution(weights):
    answer = 0
    #각 요소의 개수를 구해준다. 
    counter = Counter(weights)
    
    for key, value in counter.items():
        #특정 무게가 2명 이상이라는 것 = 같은 무게가 동일한 사람이라는 뜻. vC2를 구한다.
        if value >= 2:
            answer += value*(value-1) / 2
    
    #동일 무게를 체크해주었으니 중복 제거 해주자. 
    weights = set(weights)
    
    for w in weights:
        if w*2/3 in weights:
            answer += counter[w*2/3] * counter[w]
        if w*1/2 in weights:
            answer += counter[w*1/2] * counter[w]
        if w*3/4 in weights:
            answer += counter[w*3/4] * counter[w]    
    
    return answer

문제를 풀이하기 전에 간단히 설명하자면 
collections 라이브러리의 Counter 클래스는 파이썬의 내장 클래스로, 반복 가능한(iterable) 객체의 요소들의 개수를 셀 때 유용하게 사용된다. 마치 이 문제를 풀어주기 위해 존재하는 라이브러리처럼 ㅋㅋ 

Counter(weights)를 하면 각 요소들을 세어 Counter 객체를 생성한다.
counter.items()는 weights의 포함되어 있는 요소들의 개수를 k:v(요소:개수) 쌍의 튜플 형태로 반환해 준다. 
위의 예시대로라면,  Counter({100:3, 150:2})의 형태임을 알 수 있다.

counter [w] = w의 무게를 가지는 요소의 개수를 반환해 준다. 
counter = set(counter)는 중복을 제거하기 위함임을 간단하게 확인할 수 있다. 

1:1인 경우 
value값이 2 이상이라는 뜻은 같은 무게를 가진 사람이 다수라는 뜻이다. 따라서 위의 공식을 그대로 적용하여 nC2를 계산하여 더해준다. 

그 외의 비율인 경우
각 비율의 해당하는 요소의 개수끼리 서로 곱하여 더해준다.