[BOJ] 합이0 3151.java

 문제

- N개의 숫자(-10000~10000)가 주어질 때, 세 개의 숫자 합이 0이되는 경우의 수

 

 

 해설 및 코드

package BAEKJOON;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class 합이0_3151 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		// 2 -5 2 3 -4 7 -4 0 1 -6
		int[] arr = new int[N];

		// -7 -6 -5 -4
		ArrayList<Integer> minus = new ArrayList<>();
        
		// 1 2 2 3 7
		ArrayList<Integer> plus = new ArrayList<>();
        
        // 0은 따로

		long zero = 0;
		for (int i = 0; i < N; i++) {
			arr[i] = sc.nextInt();

			if (arr[i] == 0) {
				zero++;
			} else if (arr[i] > 0)
				plus.add(arr[i]);
			else
				minus.add(-arr[i]);

		}

		long result = 0;

		// 최대 합이 20000이므로, 20000이상은 넘어가지 않는다.
		long[] plus2 = new long[20001];
		long[] minus2 = new long[20001];


		// 조합
		for (int i = 0; i < plus.size(); i++) {
        	//plus의 i번째와 j번째를 더했을 때의 개수
			for (int j = i + 1; j < plus.size(); j++) {
				plus2[plus.get(i) + plus.get(j)]++;
			}
		}
        
        // minus에 plus의 두 개의 값을 합한 값과 같은 것이 있는 지 판단
		for (int i = 0; i < minus.size(); i++) {
			result += plus2[minus.get(i)];
		}

		for (int i = 0; i < minus.size(); i++) {
			for (int j = i + 1; j < minus.size(); j++) {
				minus2[minus.get(i) + minus.get(j)]++;
			}
		}
		for (int i = 0; i < plus.size(); i++) {
			result += minus2[plus.get(i)];
		}

		//zeroC3 조합 공식
        //zero만 택했을 경우
		if (zero >= 3) {
			// zero!/(zero-3)! * 3!
			// zero * zero-1 * zero-2 / 6
			result += (zero * (zero - 1) * (zero - 2)) / 6;

		}

		//0 + plus + minus = 0인 경우
		if (zero >= 1) {
			for (int i = 0; i < plus.size(); i++) {
				for (int j = 0; j < minus.size(); j++) {
					System.out.println(plus.get(i).equals(minus.get(j)));
					if ((int) plus.get(i) == (int) minus.get(j)) {
						result += zero;
					}
				}

			}
		}

		System.out.print(result);
	}
}

 

상당히 애를 먹은 문제이다. 스터디원의 도움으로 겨우겨우 이해할 수 있었던 문제

해당 문제는 3개의 값을 더했을 때, 0이되는 경우를 찾으면 된다.

그럴 때 가능한 경우는

1. plus + plus + minus = 0
2. minus + minus + plus = 0
3. 0 + minus + plus = 0
4. 0 + 0 + 0 = 0

총 4가지의 경우만 존재한다.

 

1, 2번

1번과 2번의 경우는 가장 Basic한 경우로 먼저 해당하는 숫자를 구해준다.

위의 예시에서 (편의상 정렬 된 형태로 가정)

ArrayList<Integer> plus의 내부는 1 2 2 3 7가 담겨있다.

그러면 해당 plus에서 2개의 값을 뽑아 만들 수 있는 조합은 각각 아래 plus2와 같이 나오게 된다.

plus2의 경우를 보게 되면 두 개의 값을 더해서 나올 수 있는 값의 개수를 세주었다.

plus2[3]은 2의 값을 가지고 plus[8]은 1의 값을 가지게 된다. 숫자가 없으면 0을 가진다.

이렇게 만든 plus2의 배열에 minus를 순회했을 때, plus2의 값이 1이상의 값을 가지면 0을 만들 수 있다는 것이 된다.

minus + minus + plus도 같은 방식으로 접근한다.

 

3번 (0+plus+minus)

3번의 경우 zero가 반드시 1개 이상일 때, 세주어야 한다.

0이 없으면 성립이 되지 않는 경우이기 때문

plus와 minus에 같은 값이 존재하는 지 검색하면 된다.

 

4번 (0+0+0)

0이 3개 이상일 때만 가능하다.

0 0 0 0 0 이면, 5C3을 계산해주면된다.

 

위 모든 경우를 더해서 result를 출력하면 된다.

 

Java 문법 정리

Integer a = 10000;
Integer b = 10000;

System.out.println(a == b);

Integer의 경우 class 객체이므로 해당 출력은 false가 나올 수 있다.

위 코드에서 (int)plus.get(i) == (int)minus.get(i)를 했을 때, false가 나와서 계속 실패했다.

Integer 형식인 경우 equal을 사용해서 비교해줘야 이러한 예외가 발생하지 않는다.