[Lv.2] 시소 짝꿍 [프로그래머스_코딩테스트] [구현] [20분]

🔍 문제 요약

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

프로그래머스

시소가 있다고 하고 중심으로 부터 2,3,4의 거리가 떨어진 곳에 weights의 무게 배열인 사람들을 배치를 시켜서 무게 * 거리가 동일한 경우 짝꿍을 이룬다고 한다. 이러한 짝꿍이 이뤄지는 경우 몇쌍이 존재하는지 반환하는 문제

🧠 나의 접근 방식과 시행착오

문제의 시도는 맞았는지 모르겠으나 시간초과가 계속 걸려서 다른 방식이 필요한 것을 알게 된 코드. 푸는 건 그저 직관적으로 모든 경우의 수를 반복하는 형태긴 했다. 중복되는 연산이 많아질 수 밖에 없었던 구조로 보이긴 함.

using System;
using System.Collections.Generic;

public class Solution
{
    public long solution(int[] weights)
    {
        // 2,3,4 거리가 존재
        int[] distArr = new int[] { 2, 3, 4 };
        // 한 쪽에 순서대로 2,3,4인 경우 앚히고 짝꿍이 되는 3가지 무게 케이스를 다 찾아보는 방법
        int[] lWeightArr = new int[3];
        int[] needWeightArr = new int[9];

        HashSet<(int, int)> sets = new HashSet<(int, int)>();
        
        // 왼쪽
        for (int i = 0; i < weights.Length; i++)
        {
            // 3개의 가능성 모두 넣어보기
            for (int k = 0; k < distArr.Length; k++)
            {
                lWeightArr[k] = weights[i] * distArr[k];
                
                for (int t = 0; t < distArr.Length; t++)
                {
                    needWeightArr[k * 3 + t] = lWeightArr[k] / distArr[t];
                }
            }

            for (int j = 0; j < weights.Length; j++)
            {
                if (i == j || sets.Contains((i, j)) || sets.Contains((j, i))) continue;

                if (Array.Exists(needWeightArr, x => x == weights[j]))
                {
                    sets.Add((i, j));
                }
            }
        }
        
        return sets.Count;
    }
}

✅ 풀이 코드

피드백으로 받은 풀이 코드. 무게와 무게의 짝의 비율을 고려 해서 1:1, 2:3, 2:4, 3:4의 가능성을 체크하는 것으로 보인다. counter 캐시에 일단 들어가지 않은 경우 다 집어 넣고, 상대의 무게가 가능한 경우 (conter.ContainsKey(무게)) 체크해서 answer를 증가시킨다. 순회를 한 번만 돌릴 수 있어서 매우 효율적으로 보이는 코드다. weights가 100,000이나 되다보니 아무래도 2중 중첩만 되도 부담이 되는 구조였던 듯 하다. 그래서 Dictionary에 미리 집어 넣고 그 다음 무게로 순회를 하면서 비율이 맞는 케이스가 있으면 경우의 수를 더하는 구조로 보인다. 문제의 핵심은 아무래도 이 서로의 비율을 도출해 내서 풀이에 적용할 수 있느냐로 보인다. 그렇게 해서 순회를 줄일 수 있는 것이 베스트인 방법.

public long solution(int[] weights)
{
    long answer = 0;
    var counter = new Dictionary<int, long>();
    
    foreach (int w in weights)
    {
        // 현재까지 등장한 무게들과의 짝을 계산
        foreach (var ratio in new (int, int)[] { (1, 1), (2, 3), (2, 4), (3, 4) })
        {
            long key = (long)w * ratio.Item2 / ratio.Item1;
            if ((w * ratio.Item2) % ratio.Item1 != 0) continue; // 정수 아니면 제외

            if (counter.ContainsKey((int)key))
            {
                answer += counter[(int)key];
            }
        }

        // 현재 무게 기록
        if (!counter.ContainsKey(w))
            counter[w] = 0;
        counter[w]++;
    }

    return answer;
}

🔄 정리

문제에서 주어질때 반복문을 100,000과 같은 형태를 2중으로 전체 순회를 도는 풀이가 나온다면 다시 생각해봐야 한다. 해당 반복문을 도는 거 자체가 부하가 크기 때문에 위처럼 Dictionary 로 캐시를 해두고 쓰는 방식에 도달해야 한다.