[Lv.1] 삼총사 [프로그래머스_코딩테스트] [완전탐색] [25분]

🔍 문제 요약

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

프로그래머스

숫자의 배열 number가 주어지고 3개의 숫자를 선택해서 합이 0이되는 조합의 개수를 구하는 문제

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

단순하게 생각했다. 25분 예상이 gpt에서 적혀있었는데 한 15분 정도나 걸렸나.. 문제는 테스트 케이스 모두 통과하긴 하였다. (정직하게 그냥 푼 문제라) 그냥 3중 for문을 돌리기로 한 것. 3개의 합이 0이되는 것을 제일 생각하기 쉬운 방법은 이거라고 생각을 했다. 그나마 조금 신경을 쓴 건 반복문을 조금이라도 줄이려고 i는 number-2번째까지, j는 number-1까지 해서 한 것 뿐.. 일단 이것도 gpt에게 더 나은 방법을 물어보기로 함.

using System;

public class Solution
{
    /// <summary>
    /// 삼총사
    /// https://school.programmers.co.kr/learn/courses/30/lessons/131705
    /// </summary>
    public int solution(int[] number)
    {
        // 3개의 번호의 합이 0이면 삼총사
        int count = 0;

        // 이게 맞나..? 3개의 번호를 어떻게 픽하지 ? 3중 for문..?
        for (int i = 0; i < number.Length - 2; i++)
        {
            for (int j = i + 1; j < number.Length - 1; j++)
            {
                for (int k = j + 1; k < number.Length; k++)
                {
                    int sum = number[i] + number[j] + number[k];

                    if (sum == 0)
                    {
                        count++;
                    }
                }
            }
        }
        
        return count;
    }
}

/// <summary>
/// C# 7.3
/// </summary>
internal class Program
{
    public static void Main(string[] args)
    {
        var sl = new Solution();
        var num1 = new []{ -2, 3, 0, 2, -5 };
        var num2 = new []{ -3, -2, -1, 0, 1, 2, 3 };
        var num3 = new []{ -1, 1, -1, 1 };
        Console.WriteLine(sl.solution(num1));
        Console.WriteLine(sl.solution(num2));
        Console.WriteLine(sl.solution(num3));
    }
}

✅ 풀이 코드

문제에서 N의 개수의 제한이 13이하로 주어진 거부터 추측할 수 있었을 수도 있긴 한데, 별달리 방법이 없다고 하긴 한다. (결국 모든 숫자들을 다 순회하면서 찾아봐야 함) Linq에 있는 Combination(3)도 있다고 한 듯 하나 3중 루프로 도는거라 성능은 거의 동일하다 하니 의미는 없는 듯.. 가장 빠르게 0이되는 케이스를 찾는다거나 한 것이 아니라 모든 조합을 찾는 거라 결국 다 뒤져야 하나 봄.. 결국 해당 문제는 브루트포스하게 푸는 것이 맞다고 한다.

 

🔄 정리

3중 for문을 돌려서 모든 경우를 다 찾은 것이긴 한데 결국 이 브루트포스 방식이 옳다고 한다. 결국 모든 케이스를 찾는 경우에서 (별달리 조건이 있거나 한 것이 아닌) 전부 순회하는 것이 맞는 듯 하다. (문제에서 N의 제한을 적게 줄 듯도)