[백준 P3151] 합이 0 자바 Java

P3151 합이 0

문제

Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. 코딩 실력이 좋으면 팀워크가 떨어지고, 팀워크가 좋을수록 코딩 실력이 떨어진다. 그리고 출전하고자 하는 대회는 코딩 실력과 팀워크 모두가 중요하다.

Elly는 그녀가 가르칠 수 있는 모든 학생들의 코딩 실력을 알고 있다. 각각의 코딩 실력 Ai는 -10000부터 10000 사이의 정수로 표시되어 있다. 그녀는 팀워크와 코딩 실력이 모두 적절한 팀을 만들기 위해, 세 팀원의 코딩 실력의 합이 0이 되는 팀을 만들고자 한다. 이러한 조건 하에, 그녀가 대회에 출전할 수 있는 팀을 얼마나 많이 만들 수 있는지를 계산하여라.

N명의 학생들의 코딩 실력 Ai가 -10000부터 10000사이의 정수로 주어질 때, 합이 0이 되는 3인조를 만들 수 있는 경우의 수를 구하여라.

 

입력값

입력은 표준 입력으로 주어진다.

첫 번째 줄에 학생의 수 N이 입력된다. 두 번째 줄에 N개의 그녀가 가르칠 학생들의 코딩 실력인 Ai가 주어진다.

• 1 ≤ N ≤ 10000
• 10000 ≤ Ai ≤ 10000

10
2 -5 2 3 -4 7 -4 0 1 -6

 

출력값

표준 출력으로 그녀가 고를 수 있는 팀의 수를 하나의 정수로 출력한다.

6

 

알고리즘

학생 클래스와 배열을 만들어서 관리한다. 그 이유는 같은 ability를 가진 학생들을 다르게 취급하기 위해서 이다. (그냥 정수 배열을 만들고 학생들의 ability를 배열로 선언하는 경우 같은 능력치를 가진 학생들은 같게 취급되어 버린다)

그렇게 나눈 이후에 학생들을 능력치에 따라 정렬하였다. 각 팀에는 총 3명의 학생들이 존재하므로 3명이 될 수 있는 조합을 찾아야 한다. 이때 모든 팀원의 능력치는 0이 되어야 하므로 먼저 선택된 두 명의 능력치의 합을 더하고 이후에 순차적으로 학생들의 능력치를 더해보면서 0이되는 경우를 카운팅 한다. 이때 학생들은 능력치를 기준으로 정렬되어 있으므로, 3 명의 학생의 능력치의 합이 0보다 크다면 더 이상 탐색하지 않고 다음 학생으로 넘어간다.

 

실패

두 명은 이미 선택되었기에 나머지 하나의 학생을 고르는 방식으로 코드를 구현했다. 선택된 두 명을 제외한 학생들을 앞에서부터 순차적으로 탐색하면서 (이미 정렬되어 있으므로) 3명의 학생의 합이 0보다 작으면 다음 학생을 탐색, 0이면 경우의 수를 추가했고, 0보다 크면 탐색을 멈췄다. 0인 경우에 따로 탐색을 멈추지 않은 이유는 (0, 0, 0, 0, 0)과 같이 같은 능력치를 가진 학생이 여러 명인 경우도 고려하기 위해서 이다. 하지만 이 풀이는 시간 초과로 이어졌다. 

 

 

성공

그래서 이분 탐색을 응용했다. 이분 탐색을 이용하여 LowerBound와 UpperBound를 구현했다. LowerBound는 찾고자 하는 값 이상이 처음 나타나는 위치이다.

public static int lowerBound(int left, int right, long target) {
    while (left < right) {
        int mid = (left + right) / 2;
        if (target <= people[mid].ability) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

 

UpperBound는 찾고자 하는 값보다 큰 값이 처음으로 나타나는 위치이다.

public static int upperBound(int left, int right, long target) {
    while (left < right) {
        int mid = (left + right) / 2;
        if (target < people[mid].ability) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

두 명의 학생은 고정되어 있기 때문에 마지막 학생이 될 수 있는 능력치의 값은 정해져 있다. 따라서 이분 탐색 LowerBound와 UpperBound를 이용하여 그 값이 처음 등장하는 인덱스와 그 값보다 큰 값이 처음 등장하는 곳의 차이를 더해주었다.

시간 복잡도는 아마 n^2 * log n 일 것이다.

 

코드

import java.util.*;
import java.io.*;

public class Main {

    static int N;
    static Student[] people;
    static long answer;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        people = new Student[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            people[i] = new Student(Integer.parseInt(st.nextToken()));
        }

        Arrays.sort(people);

        for (int current = 0; current < N; current++) {
            for (int front = current + 1; front < N; front++) {
                long teamAbility = -1 * (people[current].ability + people[front].ability);
                int cnt = upperBound(front + 1, N, teamAbility) - lowerBound(front + 1, N, teamAbility);
                answer += cnt;
            }
        }
        System.out.println(answer);
    }

    public static int lowerBound(int left, int right, long target) {
        while (left < right) {
            int mid = (left + right) / 2;
            if (target <= people[mid].ability) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    public static int upperBound(int left, int right, long target) {
        while (left < right) {
            int mid = (left + right) / 2;
            if (target < people[mid].ability) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

class Student implements Comparable<Student> {
    long ability;

    Student(long ability) {
        this.ability = ability;
    }

    @Override
    public int compareTo(Student st) {
        return Long.compare(ability, st.ability);
    }
}