문제 링크

문제 링크

문제 설명

제한사항

입출력 예

입출력 예 설명

풀이

1. 제한사항에 몸무게 배열의 길이가 100000만이라 생각없이 이중포문 돌리다가 망한다.
2. 힌트가 하나 있는데, weight의 종류?를 제한해준것이다. (100부터 1000까지 901개)
3. map에다가 최대 10만명의 사람들을 <몸무게, 명수>로 정리한다.
4. 이제, 짝꿍을 구하는 로직을 짜야하는데 2, 3, 4라는 배율을 가지고 서로다른(map으로 중복 제거했으니) 두 몸무게를 비교할 수 있는 모든 경우의 수는 총 여섯가지가 나왔다.
   4-1 다른 사람의 풀이를 보니까 4가지?로 줄이긴하던데 일단 나는 여섯가지 모두 대조해보았다.
5. 이제 배열 사이즈를 최대 1000개로 줄여놨으니, 이중포문 정도는 부담이 없다.
6. 그래서 짝꿍 구하는 함수(isFreind)를 통과하면 양쪽의 value를 곱해주자.
7. 여기서 같은 몸무게인 사람들의 수가 1보다 크면, 이 사람들끼리 짝꿍이 되는 경우도 더해주어야한다.

아 이 문제가 왜이렇게 어려웠을까...?

O(n)에 풀고싶었던 욕심이 너무 컸었나.. 계속 그쪽 풀이로 생각하다가 다른 생각이 막혀버린것 같다.

그러다가 시간이 좀 너무 지체되는거 같아서 가장 직관적인 방법이었던 이 방법으로 바로 풀긴했는데 그래도 아쉬움이 좀 많이 남는 풀이다.

코드

import java.util.*;
class Solution {
    public boolean isFriend(Integer f1, Integer f2) {
        return (f1 * 2 == f2 * 3) || (f1 * 2 == f2 * 4 )|| (f1 * 3 == f2 * 2) || (f1 * 3 == f2 * 4) || (f1 * 4 == f2 * 2) || (f1 * 4 == f2 * 3);
    }
    public long solution(int[] weights) {
        long answer = 0;
        Map<Integer, Integer> wmap = new HashMap<>();
        for(int weight : weights) 
        {
            wmap.put(weight, wmap.getOrDefault(weight, 0) + 1);
        }
        Integer[] weight = wmap.keySet().toArray(new Integer[wmap.size()]);
        Integer[] num = wmap.values().toArray(new Integer[wmap.size()]);
        int i, j;
        for(i = 0; i < weight.length - 1; i++) {
            if(num[i] > 1) {
                answer += (long) num[i] * (num[i] - 1) / 2;
            }
            for(j = i + 1; j < weight.length; j++) {
                if(isFriend(weight[i], weight[j]))
                {
                    answer += (long)num[i] * num[j];
                }
            }
        }
        if(num[i] > 1)
            answer += (long) num[i] * (num[i] - 1) / 2;
        return answer;
    }
}