시소 짝꿍

 

 

---

 

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

프로그래머스

 

---

 

분석

 

---

 

DFS로 풀기: 재귀함수 -> 시간 초과

public class 시소짝꿍 {

	public static void main(String[] args) {
		Solution solution = new Solution();
		int[] arr = {100, 180, 360, 100, 270};
		long result = solution.solution(arr);
		System.out.println(result);//4

	}

	static class Solution {
		int totalCount = 0;

		public long solution(int[] weights) {
			for (int i = 0; i < weights.length - 1; i++) {
				for (int j = 1; j < weights.length - 1; j++) {
					DFS(i, j, weights);
				}
			}

			return totalCount;
		}// solution func end

		private void DFS(int start, int end, int[] weights) {
			// 처음 골랐을때 같은 경우
			if (weights[start] == weights[end]) {
				totalCount++;
				return;
			}

			// 서로 다른 경우 거리를 곱해서 같은 값을 찾는다
			// 찾은 경우
			if (DFS2(weights[start], weights[end])) {
				totalCount++;
				return;
			}

		}// DFS func end

		private boolean DFS2(int start, int end) {
			int[] distanceArr = {2, 3, 4};

			for (int i = 0; i < distanceArr.length - 1; i++) {
				if (start * distanceArr[i] == end * distanceArr[i + 1]) {
					return true;
				}
			}
			return false;
		}// DFS2 func end


	}// Solution class end

}// one class end

 

 

---

 

O(N)으로 하기 위해 HashMap 사용 -> 실패

경우의 수 3개

 

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class 시소짝꿍3_중복제거 {

	public static void main(String[] args) {
		Solution solution = new Solution();
		int[] arr = {100, 180, 360, 100, 270};
		long result = solution.solution(arr);
		System.out.println(result);//4

	}

	static class Solution {
		public long solution(int[] weights) {
			Arrays.sort(weights);

			ArrayList<Integer> duplicatedKeyList = new ArrayList<>();
			Map<Integer, Integer> map = new HashMap<>();// 무게, 갯수

			for (int w : weights) {
				map.compute(w, (key, value) -> value == null ? 0 : value + 1);

			}
			System.out.println(map);

			// 같은 숫자 제거, 중복 제거
			for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
				if (entry.getValue() >= 1) {
					duplicatedKeyList.add(entry.getKey());
					entry.setValue(0);
				}
			}

			System.out.println(map);

			for (int w : map.keySet()) {

				if (map.containsKey(w * 2)) {
					map.computeIfPresent(w * 2, (key, value) -> value + 1);
				}

				if (map.containsKey(w * 3 / 2)) {
					map.computeIfPresent(w * 3 / 2, (key, value) -> value + 1);

				}

				if (map.containsKey(w * 4 / 3)) {
					map.computeIfPresent(w * 4 / 3, (key, value) -> value + 1);
				}

			}

			long sum = 0;

			for (int value : map.values()) {
				sum += value;
			}

			return sum + duplicatedKeyList.size();
		}// func solution end


	}// Solution class end

}// one class end

 

---

 

 

HashMap 함수 -> 이게 정답이라는데

테스트 케이스

 

배수 목록 [1배, 1/2배, 2/3배, 3/4배]

[100, 50, 100, 150] // return 5;

 

(100, 50) -> 인덱스 0, 1

(100, 100) -> 인덱스 0, 2

(100, 150) -> 인덱스 0, 3--->  애 안됨

 

(100, 100) -> 인덱스 2, 0

(100, 50) -> 인덱스 2, 1

(100, 150) -> 인덱스 2, 3 --> 애 안됨

 

(150, 100) -> 인덱스 3, 0

(150, 50) -> 인덱스 3, 1  --> 애 안됨

(150, 100) -> 인덱스 3, 2

 

-----------------------------------------------

(100, 50) -> 인덱스 0, 1

 

(100, 100) -> 인덱스 0, 2 ---> 중복

(100, 100) -> 인덱스 2, 0 ---> 중복

 

(100, 50) -> 인덱스 2, 1

(150, 100) -> 인덱스 3, 0

(150, 100) -> 인덱스 3, 2

-----------------------------------------------

return 5;

 

 

 

조합 사용 풀이

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
class Solution {
    public long solution(int[] weights) {
            // 무게 빈도를 저장하는 해시맵
            Map<Integer, Long> weightCount = new HashMap<>();
            
            // 무게의 빈도를 기록
            for (int weight : weights) {
                weightCount.put(weight, weightCount.getOrDefault(weight, 0L) + 1);
            }

            long totalCount = 0;

            // 모든 무게에 대해 짝꿍을 찾아본다
            for (Map.Entry<Integer, Long> entry : weightCount.entrySet()) {
                int weight1 = entry.getKey();
                long count1 = entry.getValue();

                // 동일한 무게의 조합 수를 계산 (kC2)
                totalCount += (count1 * (count1 - 1)) / 2;

                // 다른 무게와의 조합을 검사
                for (int weight2 : weightCount.keySet()) {
                    if (weight1 >= weight2) continue; // 중복 방지

                    long count2 = weightCount.get(weight2);

                    // (2, 3), (2, 4), (3, 4) 거리 조합을 확인
                    if (weight1 * 2 == weight2 * 3 || weight1 * 3 == weight2 * 2 ||
                        weight1 * 2 == weight2 * 4 || weight1 * 4 == weight2 * 2 ||
                        weight1 * 3 == weight2 * 4 || weight1 * 4 == weight2 * 3) {
                        totalCount += count1 * count2;
                    }
                }
            }

            return totalCount;
        }
           
}

 

 

다른 풀이

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
class Solution {
    public long solution(int[] weights) {
        long answer = 0;
        Arrays.sort(weights);
        HashMap<Double,Integer> map = new HashMap<>();
        for(int w : weights){
            double a = (double)w;
    		double b = ((double)w*2.0)/3.0;
    		double c = (double)w/2.0;
    		double d = ((double)w*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(a, map.getOrDefault(a, 0)+1);
        }
        return answer;
    }
}

출처: https://blog.naver.com/tlstjd436/223142633640?trackingCode=rss