백준 3151번: 합이 0 (JAVA)

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

3151번: 합이 0

문제

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

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

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

입력

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

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

출력

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

제한

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

 

---

 

풀이

풀이 1. 이분 탐색 (혹은 투 포인터로 푸는 방법)

인터넷에 있으니 보면 된다. 아무리 생각해도, 해싱이 되는데 굳이 이분탐색을 해야하나 싶다. O(N^2)를 놔두고 O(N^2logN)을 쓰긴 살짝 찝찝하다.

(4/13 추가: HashMap 개느리다! 위험하다고 생각하면 binary search / two pointers 풀이가 낫다.)

 

 

풀이 2. 내 풀이

주어진 값을 음수, 0, 양수로 나눠서 저장한다. 저장하면서, 각 원소의 등장 횟수를 배열에 기록한다: 주어지는 값의 범위가 -10000 ~ 10000이므로 가능.

합이 0이 되는 방법은 크게 4가지가 있다: 1) 0+0+0, 2) 음수+0+양수 3) 양수+양수+음수, 4) 양수+음수+음수.

1) case는 배열에 0이 3개 이상인 경우에만 가능하다: 0이 n개일 때, nC3으로 구하면 된다. (Note: 10000C3 > 2^32이니 정답은 long type으로 저장해야 한다.)

2)~4) case: 음수 배열에서 원소 1개, 양수 배열에서 원소 1개를 뽑은 후, -(두 원소의 합)이 0이면 2), 양수면 3), 음수면 4) 케이스에 해당한다. 원소 개수를 미리 세두었으니 몇 가지 경우가 있는지 알 수 있다.

2) case의 경우, 중복하여 세어지지 않는다.

3), 4) case의 경우, 2번 중복하여 세어지게 된다: 나중에 2로 나누어야 한다.

 - 그리고, -(두 원소의 합)이 뽑은 원소랑 같은 경우, (횟수 - 1)만큼을 더해야 한다.

 

조금 경우가 많고 말로 보니 복잡한 느낌이 있는데, 그렇게 복잡하지 않으며 직관적인 편이다.

 

 

풀이 3. 기똥찬 풀이 (JusticeHui 선생님 코드 참고)

풀이 2에서 자질구레하게 경우를 나누었던 것은, 중복되는 횟수가 case마다 다르기 때문이었다. 이를 세 수의 합이 완성되는 맨 뒤의 인덱스에서만 센다는 아이디어로 해결하였다.

설명은 생략: 코드 참고.

 

 

코드

풀이 2

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] counter = new int[20001];
        StringTokenizer st = new StringTokenizer(br.readLine());
        List<Integer> pos = new ArrayList<>();
        List<Integer> zero = new ArrayList<>();
        List<Integer> neg = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            int temp = Integer.parseInt(st.nextToken());
            if (temp > 0) pos.add(temp);
            else if (temp < 0) neg.add(temp);
            else zero.add(temp);
            counter[temp+10000]++;
        }

        long ans = 0;
        long zeros = 0;
        for (int minus: neg) {
            for (int plus: pos) {
                if (-minus-plus == 0) zeros += counter[10000];
                else if (-minus-plus == plus || -minus-plus == minus) ans += counter[10000-minus-plus]-1;
                else ans += counter[10000-minus-plus];
            }
        }
        zeros += comb(zero.size(), 3);
        System.out.println(ans/2 + zeros);
    }


    static long comb(int n, int r) {
        if (n < r) return 0;

        long ret = 1;
        for (int i = n; i > n - r; i--) {
            ret *= i;
        }
        return ret / 6;
    }
}

 

 풀이 3

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] counter = new int[40001];
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] nums = new int[N];

        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        long ans = 0;
        for (int i = 0; i < N; i++) {
            ans += counter[20000-nums[i]];
            for (int j = 0; j < i; j++) {
            // 두 원소를 더하기 때문에 counter의 범위는 40000으로
                counter[20000+nums[i]+nums[j]]++;
            }
        }
        System.out.println(ans);
    }

}