[BaekJoon] 3151 합이 0 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N;
    static int[] codingSkills;

    static void input() {
        Reader scanner = new Reader();

        N = scanner.nextInt();
        codingSkills = new int[N];

        for(int student = 0; student < N; student++)
            codingSkills[student] = scanner.nextInt();
    }

    static void solution() {
        Arrays.sort(codingSkills);

        long answer = 0L;
        for(int student = 0; student < N; student++)
            answer += twoPointer(student + 1, N - 1, codingSkills[student] * (-1));

        System.out.println(answer);
    }

    static long twoPointer(int left, int right, int target) {
        long count = 0;
        while(left < right) {
            int sum = codingSkills[left] + codingSkills[right];
            
            if(sum == target) {
                if(codingSkills[left] == codingSkills[right]) {
                    int sameNum = right - left + 1;
                    count += sameNum * (sameNum - 1) / 2;
                    break;
                }
                
                int sameLeftNum = 1, sameRightNum = 1;
                
                while(codingSkills[left] == codingSkills[left + 1]) {
                    left++;
                    sameLeftNum++;
                }
                
                while(codingSkills[right] == codingSkills[right - 1]) {
                    right--;
                    sameRightNum++;
                }
                
                count += sameLeftNum * sameRightNum;
            }

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

        return count;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 주어진 코딩 실력을 투포인터를 이용하기 위해 오름차순으로 정렬합니다.
• 첫 번째 코딩 실력부터 마지막까지 순회하며 해당 코딩 실력과 합했을 때 0이 되는 두 코딩 실력을 투포인터를 통해 찾습니다.
  • 투포인터로 탐색할 범위는 현재 코딩 실력 바로 다음부터 마지막까지가 됩니다.
    • 이전 코딩 실력들을 탐색할 범위에 추가하면 중복이 발생하기 때문에 제외시킵니다.
  • 왼쪽 포인터와 오른쪽 포인터에 해당하는 코딩 실력을 더하고 그 값이 {현재 코딩 실력 * (-1)}과 같은지 확인합니다.
    • 만약 같다면 그 두 학생은 현재 코딩 실력에 해당하는 학생과 팀을 이룰 수 있다는 뜻이 됩니다.
      • 이 때, 왼쪽 포인터에 해당하는 코딩 실력과 같은 코딩 실력을 가지는 학생들이 있을 수 있고, 오른쪽 포인터에 해당하는 코딩 실력과 같은 코딩 실력을 가지는 학생들 또한 있을 수 있습니다.
      • 그 학생들 모두 현재 코딩 실력에 해당하는 학생과 팀을 이룰 수 있기 때문에 그 학생들의 수를 각각 찾고, 그 학생들의 수를 곱한 값을 현재 학생과 팀을 이룰 수 있는 학생들의 경우의 수에 추가합니다.
      • 그리고 왼쪽 포인터와 오른쪽 포인터는 같은 점수가 아닌 학생이 처음 나오는 곳으로 각각 이동시킵니다.
    • 만약 더한 코딩 실력이 더 작거나 같다면 코딩 실력의 합을 올려주기 위해 왼쪽 포인터를 하나 증가시킵니다.
    • 만약 더한 코딩 실력이 더 크다면 코딩 실력의 합을 낮추기 위해 오른쪽 포인터를 하나 낮춥니다.
• 위 과정을 통해 나온 경우의 수들을 모두 더하여 최종 답을 구합니다.