C# [프로그래머스] Lv.1 삼총사

 

삼총사 


제한사항

number = 검사해야 할 정수 배열 인덱스

result = 특정 합을 충족하는 삼총사의 갯수

 

 

 

어제 풀었던 숫자 짝꿍에서 시간 복잡도에서 계속 발목 잡혔던것 맘에 걸려 

 

문제를 보고 처음으로 떠올랐던 3중 for문을 돌리는 방식이 아닌 

 

특정 배열의 합을 구할때 용이한 Two Pointer 알고리즘을 활용하면 
특정한 합을 가지는 부분 수열을 찾기 용이할 것 같아 활용해서 풀어보았다.

 

 

 

 public class Solution
 {
     public int solution(int[] number)
     {
         int answer = 0;
         Array.Sort(number);

         for(int i = 0; i < number.Length - 2; i ++) // start와 end 인덱스가 i에서 +1되고 Length에서 -1 됨으로 두바퀴를 덜 돌아도 됨.
         {
             int index_Start = i + 1;
             int index_End = number.Length - 1; // 인덱스는 0부터 시작이므로 -1

             while (index_Start < index_End)
             {
                 int sum = number[index_Start] + number[index_End] + number[i];
                 
                 if (sum == 0)
                 {
                     answer++;
                     
                     index_End--;
                 }
                 else if (sum < 0)
                 {
                     index_Start++;
                 }
                 else
                 {
                     index_End--;
                 }
             }
         }

         return answer;
     }

 }

 

 

이후 테스트 케이스를 돌려보고 정답 체크까지 해보았으나

 

 

 

 

 

일부 테스트 지문에서 통과를 못했다....

 

추측건대 아마 0과 1이 아주 아주 길게 반복된 지문에서는 경우의 수를 모두 탐색할 수 없는게 

 

첫번째로 든 생각이었다.

 

반례를 모두 확인 할 방법이 없었다.

 

사실 Two Pointer 알고리즘은 배열 내의 3개 이상의 수를 비교하거나 이 숫자들이 연속되지 않을때에는 

i값의 변경과 start와 end index를 계속 변경하며 체크하는 과정이 매끄럽지 않고 

 

Two Pointer를 사용하기 적합하지 않은 사례라는 영상과 글을 보고 다른 방법으로 진행하기로 마음먹었다.

 

public int solution(int[] number)
{
    int answer = 0;
    
    for (int i = 0; i < number.Length; i ++)
    {
        for (int j = i + 1; j < number.Length; j ++)
        {
            for(int k = j + 1; k < number.Length; k ++)
            {
                if (number[i] + number[j] + number[k] == 0)
                {
                    answer++;
                }
            }
        }
    }
    return answer;
}

 

 

Two Pointer로 문제를 푸는데에는 실패 했지만 

 

단순하게 for문이나 if문의 반복으로 문제를 푸는 것 보다

 

당장에는 어렵고 실패하더라도 여러 알고리즘 기법을 활용해서 푸는 버릇을 길러야 겠다는 생각을 했다.

 

난이도가 올라 갈수록 시간복잡도와 반례를 따져보며 보다 꼼꼼하게 경우의 수를 따져야 하는게 실감난다.