20250305

코딩테스트

삼총사

프로그래머스

 

내가 작성한 코드

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

    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++) {
          if (number[i] + number[j] + number[k] == 0) {
            System.out.println(number[i] + " " + number[j] + " " + number[k]);
            answer += 1;
          }
        }
      }
    }
    return answer;
    }
}

 

 

한 개의 1차원 배열 안에는 임의의 정수들이 존재한다. 이때 배열 안에 있는 세 개의 정수를 더해 0이 되는 갯수를 구하는 문제이다.

단, 세 개의 정수를 더 해 0이 되는 숫자는 중복되어서는 안된다.예를 들어 {-2, 0 ,2}는 {-2, 2, 0}와 동일하게 취급하므로 개수는 1개로 취급한다.

 

제한 사항에서 input 최대 크기가 13으로, 삼중 반복문을 사용하기에 크기가 크지 않은 덕분에 위의 코드로 문제를 해결할 수 있었다. 그러나 만약 더 많은 정수나 더 큰 배열의 크기를 고려해야 한다면 지금의 (O(n³)) 만으로는 해결할 수 없다.

 

최적화된 코드

일반적으로 입력 크기가 커질 가능성이 있다면 투 포인터(two pointer)를 활용한 O(n²) 방식이 더 효율적이다.

import java.util.Arrays;

class Solution {
    public int solution(int[] number) {
        int answer = 0;
        Arrays.sort(number);  // 정렬
        
        for (int i = 0; i < number.length - 2; i++) {
            int left = i + 1;
            int right = number.length - 1;
            while (left < right) {
                int sum = number[i] + number[left] + number[right];
                if (sum == 0) {
                    // sum이 0인 경우, 왼쪽과 오른쪽에 중복되는 값이 있다면 경우의 수를 모두 더해야 함
                    if (number[left] == number[right]) {
                        // left와 right 사이에 있는 모든 수가 같다면 조합의 수는 nC2
                        answer += (right - left + 1) * (right - left) / 2;
                        break;
                    } else {
                        int leftCount = 1;
                        int rightCount = 1;
                        while (left + 1 < right && number[left] == number[left + 1]) {
                            leftCount++;
                            left++;
                        }
                        while (right - 1 > left && number[right] == number[right - 1]) {
                            rightCount++;
                            right--;
                        }
                        answer += leftCount * rightCount;
                        left++;
                        right--;
                    }
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return answer;
    }
}