시소 짝꿍

2026.07.09

문제 풀이

1차 실행 오류

---

23.5/100

실패 및 시간 초과 오류

---

알고리즘 분석

반복문으로 비교해가며 두 수의 최대공약수를 구한 후,
비율을 구해서 a : b에서 a, b가 각각 1 ~ 4의 범위 내에 있으면
짝꿍으로 가능하고, 그 이상이라면 불가능함

---

AI를 통한 원인 분석

→ 현재 좌석은 2, 3, 4만 존재하며 1은 존재하지 않음
따라서 1:3, 1:4 또는 3:1, 4:1의 비율은 불가능함

---

class Solution {
    public long gcd(long a, long b) { // 최대공약수를 구하는 함수
        return b == 0 ? a : gcd(b, a % b);
    }
    public long solution(int[] weights) {
        int result = 0;
        for (int i = 0; i < weights.length; i++) {
            for (int j = i + 1; j < weights.length; j++) {
                long a = weights[i];
                long b = weights[j];
                long g = gcd(a, b); // 최대공약수
                
                a /= g;
                b /= g;
                
                if (a > 0 && a <= 4 && b > 0 && b <= 4) {
                    result++;
                }
            }
        }
        return result;
    }
}

2차 실행 오류

---

41.2/100

시간 초과 오류

---

이전 실패 해결

a == 1 or b == 1일 때, b or a가 2를 넘어가지 않는 조건 추가

---

class Solution {
    public long gcd(long a, long b) { // 최대공약수를 구하는 함수
        return b == 0 ? a : gcd(b, a % b);
    }
    public long solution(int[] weights) {
        long result = 0;
        for (int i = 0; i < weights.length; i++) {
            for (int j = i + 1; j < weights.length; j++) {
                long a = weights[i];
                long b = weights[j];
                long g = gcd(a, b); // 최대공약수
                
                a /= g;
                b /= g;
                
                if (a > 0 && a <= 4 && b > 0 && b <= 4) {
                    if ((a == 1 && b > 2) || (b == 1 && a > 2)) {
                        continue;
                    }
                    result++;
                }
            }
        }
        return result;
    }
}

3차 실행 오류

---

76.5/100

실패

---

AI를 통한 원인 분석

int 사용으로 인한 오버플로우 발생

---

현재 코드 분석(AI 알고리즘 추천 및 본인 구현)

2 <= weights <= 100,000의 범위를 갖는 배열 대신
100 <= weights[i] <= 1000의 범위를 갖는 몸무게에 대해서

사람들의 각 몸무게에 대한 인원 수와,
각 몸무게에 대해 가능한 비율을 저장하여 사람 수를 셈

---

import java.util.Map;
import java.util.HashMap;

class Solution {
    public long solution(int[] weights) {
        Map<Integer, Integer> map = new HashMap<>();
        int[][] ratio = {{1, 2}, {2, 1}, {2, 3}, {3, 2}, {3, 4}, {4, 3}};
        long result = 0;
        
        for (int i = 0; i < weights.length; i++) { // 몸무게 별 사람 수 저장
            map.put(weights[i], map.getOrDefault(weights[i], 0) + 1);
        }
        
        for (Integer w : map.keySet()) {
            for (int j = 0; j < ratio.length; j++) {
                int p = ratio[j][0];
                int q = ratio[j][1];
                
                int n = (w * q) / p;
                
                if ((w * q) % p == 0 && n >= 100 && n <= 1000) {
                    Integer r = map.get(n);
                    if (r != null) {
                        result += (long) map.get(w) * r;   
                    }
                }
            }
        }
        result /= 2;
        for (Integer key : map.keySet()) {
            int w = map.get(key);
            
            result += (w * (w - 1)) / 2;
        }
        
        return result;
    }
}

정답 코드

소요 시간: 1시간 53분

시간 복잡도: $O(n)$

import java.util.Map;
import java.util.HashMap;

class Solution {
    public long solution(int[] weights) {
        Map<Integer, Integer> map = new HashMap<>();
        int[][] ratio = {{1, 2}, {2, 1}, {2, 3}, {3, 2}, {3, 4}, {4, 3}};
        long result = 0;
        
        for (int i = 0; i < weights.length; i++) { // 몸무게 별 사람 수 저장
            map.put(weights[i], map.getOrDefault(weights[i], 0) + 1);
        }
        
        for (Integer w : map.keySet()) {
            for (int j = 0; j < ratio.length; j++) {
                int p = ratio[j][0];
                int q = ratio[j][1];
                
                int n = (w * q) / p;
                
                if ((w * q) % p == 0 && n >= 100 && n <= 1000) {
                    Integer r = map.get(n);
                    if (r != null) {
                        result += (long) map.get(w) * r;   
                    }
                }
            }
        }
        result /= 2;
        for (Integer key : map.keySet()) {
            long w = map.get(key);
            
            result += (w * (w - 1)) / 2;
        }
        
        return result;
    }
}

AI 코드

시간 복잡도: $O(901)$

class Solution {
    public long solution(int[] weights) {
        int[][] ratio = {{1, 2}, {2, 1}, {2, 3}, {3, 2}, {3, 4}, {4, 3}};
        long[] count = new long[1001]; // 몸무게별 사람 수 (인덱스 = 몸무게)
        long result = 0;

        for (int w : weights) {
            count[w]++;
        }

        for (int w = 100; w <= 1000; w++) {
            if (count[w] == 0) continue;

            for (int[] r : ratio) {
                int p = r[0], q = r[1];
                if ((w * q) % p != 0) continue;

                int n = (w * q) / p;
                if (n >= 100 && n <= 1000 && count[n] > 0) {
                    result += count[w] * count[n];
                }
            }
        }
        result /= 2;

        for (int w = 100; w <= 1000; w++) {
            result += (count[w] * (count[w] - 1)) / 2;
        }

        return result;
    }
}