[BOJ 3151] 합이 0

문제

합이 0

https://www.acmicpc.net/problem/3151

 

 

풀이

설명

조건에 맞춰 고를 수 있는 팀의 수를 구하는 문제입니다.

 

조건은 다음과 같습니다.

• 한 팀은 세 명으로 이루어집니다.
• 팀원들의 점수의 합이 0이 되어야 합니다.

 

이 문제는 투 포인터 알고리즘을 이용해 해결할 수 있습니다.

 

과정은 다음과 같습니다.

1. 학생들을 실력 순으로 정렬합니다.
2. 첫 번째 학생(i)을 고정합니다.
3. 두 번째 학생 left(i+1)과 세 번째 학생 right(N-1)을 지정합니다.
4. 세 학생의 코딩 실력 합을 계산 후, 합에 따라서 포인터를 이동하고, 결과를 처리합니다.

 

시간복잡도는 O(n^2)이 됩니다.

 

예시 코드

function solution() {
  const TARGET = 0;

  const n = Number(input());
  const nums = input().split(" ").map(Number);
  nums.sort((a, b) => a - b);
  let answer = 0;

  // 첫 번째 학생 고정
  for (let i = 0; i < n - 2; i++) {
    let left = i + 1; // 두 번째 학생
    let right = n - 1; // 세 번째 학생

    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];

      if (sum === TARGET) {
        if (nums[left] === nums[right]) {
          // 왼쪽과 오른쪽 값이 같으면 그 사이에 있는 모든 값들은 동일하므로 조합 수 계산
          const cnt = right - left;
          answer += (cnt * (cnt + 1)) / 2;
          break;
        }

        let sameLeft = 1;
        let sameRight = 1;

        while (nums[left] === nums[left + 1]) {
          sameLeft++;
          left++;
        }
        while (nums[right] === nums[right - 1]) {
          sameRight++;
          right--;
        }

        answer += sameLeft * sameRight;

        left++;
        right--;
      } else if (sum < TARGET) left++;
      else right--;
    }
  }

  return answer;
}