프로그래머스 - 시소짝꿍

1. 문제

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

프로그래머스

 

2. 접근방식

구현 + 계수정렬을 이용해 접근하면 된다.

 

계수정렬이란?

• 입력 배열의 원소값을 계수하여 새 배열에 누적합으로 담아 정렬하며 값 비교없이 수행하는 정렬방법이다.

 

사용 가능한 조건은?

• 원소 값이 양의 정수인 경우
• 원소 최대값의 자리수가 작을 경우 -> 해당 문제에선 weights의 값 범위가 100~1000으로 작음

 

구현시 주의해야 할점은?

• 무게값이 같은 경우 -> 예를 들어 100(weights)가 4개 있을 경우 쌍이 이루어지는 경우의 수는 4가지가 아닌 3+2+1 인 6가지이다.
• 곱하기(4/3, 3/2, 2) 한 값이 여러개 인 경우 -> 예를 들어 100(weights)가 2개 200(weighs)가 3개인 경우 2*3으로 6가지 이다.

 

 

3. 구현

import java.util.*;

class Solution {
    public long solution(int[] weights) {
        long answer = 0;
        // 시소 짝꿍이 생기는 weights의 쌍 개수를 담기 위한 배열
        long[] result = new long[1001];
        // 중복된 weights들의 개수를 담기 위한 배열
        long[] duplicate = new long[1001];
        Arrays.sort(weights);
        
        for (int i=0; i<weights.length; i++) {
            duplicate[weights[i]]++;
        }
        // 중복된 weights의 값을 담지 않기 위해 Set을 사용
        Set<Integer> set = new HashSet<Integer>();
        for (int i=0; i<weights.length; i++) {
            int current = weights[i];
            if (current*2 < result.length) {
                result[current*2] += duplicate[current*2];
            }
            if ((current*3)/2 < result.length && (current*3)%2 == 0) {
                result[(current*3)/2] += duplicate[(current*3)/2];
            }
            if ((current*4)/3 < result.length && (current*4)%3 == 0) {
                result[(current*4)/3] += duplicate[(current*4)/3];
            }
            set.add(current);
        }
        int previous = 0;
        for (int i=0; i<weights.length; i++) {
            int current = weights[i];
            // 100 == 100 처럼 무게가 같은 경우의 수를 체크
            if (previous == current) {
                result[current] += --duplicate[current];
            }
            previous = current;
        }
        for (int i : set) {
            answer += result[i];
        }
        return answer;
    }
}

 

4. 정리

중복값의 반례를 생각못해 많이 헤맸다. 항상 마음을 조급하게 먹지말고 차분하게 천천히 하나씩 찾아보자