[자바] 백준 3151 - 합이 0 (java)

목차

문제 : boj3151

 

 

필요 알고리즘

• 브루트포스 (brute force)
  
  • 모든 경우를 보면 되긴한데, 효율적으로 보면 된다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  단순히 생각하면 10000C3을 전부 보면 되는데 당연히 그러면 대충 O(10000^3) 이므로 비효율적이다.

 

  약간 아이디어를 더해보자. N개의 수를 입력 받으면서 어떠한 수가 몇 번 나왔는지 미리 세두자. HashMap으로 처리해도 되고, 그냥 들어온 수에 1만을 더하면 범위가 0~20000이므로 20001개 짜리 배열로도 처리할 수 있다. 이 경우 어떠한 특정한 수가 몇 개 존재하는지는 O(1)로 판단할 수 있을 것이다.

 

  그리고 3개의 합은 O(10000^3)이지만, 2개의 합의 모든 경우를 보는데는 O(10000^2)이면 된다. 그렇다면 2개의 합을 보고, 그걸 0으로 만들 수 있는 수가 몇 개 존재하는지를 O(1)로 확인하면 3개의 합을 살펴본 셈이다.

// 입력받은걸 cnt 배열에 특정 수가 몇번 나왔는지 세두었다.
for (int i = 0; i < n; i++) {
    cnt[(arr[i] = Integer.parseInt(st.nextToken()))+10000]++;
}

long answer = 0l;
// 2중 for문으로 2개의 합의 모든 경우를 보면서
for (int i = 0; i < n; i++) {
    for (int j = i+1; j < n; j++) {
        int sum = arr[i]+arr[j];
        // 두 수의 합의 절대값이 1만을 넘는다면 버린다.
        if (Math.abs(sum) > 10000) continue;

		// 두 수의 합을 0으로 만들 수 있는 수를 결과에 더한다.
        answer += cnt[-sum+10000];
        
        // 현재 보고 있는 수와 동일한 수는 결과에서 하나씩 빼준다.
        if (-sum==arr[i]) answer--;
        if (-sum==arr[j]) answer--;
    }
}

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        int[] cnt = new int[20001];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            cnt[(arr[i] = Integer.parseInt(st.nextToken()))+10000]++;
        }

        long answer = 0l;
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                int sum = arr[i]+arr[j];
                if (Math.abs(sum) > 10000) continue;

                answer += cnt[-sum+10000];
                if (-sum==arr[i]) answer--;
                if (-sum==arr[j]) answer--;
            }
        }

        System.out.println(answer/3);
    }
}