[Lv.1] 삼총사 [프로그래머스_코딩테스트] [완전탐색] [25분]
🔍 문제 요약
https://school.programmers.co.kr/learn/courses/30/lessons/131705
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
숫자의 배열 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의 제한을 적게 줄 듯도)