[BOJ 백준] 합이 0인 네 정수(7453) C++, Java

링크 : https://www.acmicpc.net/problem/7453

7453번: 합이 0인 네 정수

 

 

문제 설명 : 

정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.

A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오.

 

입력 : 

첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 2^28이다.

 

출력 : 

합이 0이 되는 쌍의 개수를 출력한다.

 

 

예제 입력 : 

6
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45

 

예제 출력 : 

5

 

접근법 : 

1) 어떻게 풀 것인가?

4개의 숫자를 합해서 0인지 확인해야한다.

완전탐색으로 다 해볼 경우 시간복잡도는 N^4로 N이 4,000이기 때문에 시간초과가 발생한다.

 

따라서 이름 logN이나 N으로 줄이는 로직이 필요한데,

4개의 배열을 그대로 계속 사용할 경우에는 loop를 4번 돌기 때문에 현실적으로 문제 해결이 힘들다.

 

이 문제에서는 숫자의 합이 0만 되면 되기 때문에 4개의 배열을 2개씩 미리 합을 구해둬도

답에 영향을 미치지 않는다.

 

이렇게 4개의 배열 A, B, C, D를, 2개의 배열 AB의합, CD의 합으로 합쳐놓을 경우,

투 포인터를 통해 합이 0인 경우를 쉽게 구할 수 있다.

 

① AB의 합과 CD의 합을 오름차순으로 각각 정렬

② AB는 최솟값부터, CD는 최댓값부터 투 포인터 출발

③ AB+CD의 합이 0일 경우 중복인 합 개수까지 고려해서 정답에 더하기.

④ AB+CD>0인 경우 CD를 낮춰준다. (값을 줄여야 0이 되므로)

⑤ AB+CD<0인 경우 AB를 높혀준다. (값을 늘려야 0이 되므로)

 

자세한 로직은 아래 소스코드 참고.

 

그러면 배열의 합을 구하는 경우의 수 N^2 = 1,600만.

정렬 하는데 N logN.

마지막 투 포인터를 하는데 N(이 때는 1,600만)의

시간복잡도가 필요해 문제를 통과하는데는 무리없다.

 

글을 쓰다 든 생각인데

이진탐색(binary search)을 변형해 upper_bound 또는 lower_bound를 통해

답을 찾는 방식도 괜찮을 것 같다. 

 

2) 시간복잡도

두 배열씩 합을 구하는 시간 4000*4000 = 1,600만, 투 포인터 진행시 1,600만의 반복문을 진행한다.

여유롭진 않지만 통과하는데 무리는 없다.

(Java 기준 -  1,776ms)

 

3) 공간복잡도

int 4000개 * 4개 배열 + int 1600만개 * 2개 배열 = 약 int 4,800만개 배열이 든다.

4Bytes (int) * 4,800만 = 183MBytes 로 메모리를 많이 쓰는 편이지만,

메모리 제한인 256MBytes에 걸리진 않는다.

 

4) 풀면서 놓쳤던점

정답과 AB, CD count를 int형으로 했다가 오답이 발생했다.

정답의 경우 4,000 ^ 4 가 최댓값이므로 long 형태가 필요하며

중간 count의 경우 최대 1,600만이므로 int형으로 해줘도 되나,

정답에 더해줄때 곱이 발생하므로 long으로 형 변환을 해줘야한다. (아래 코드 참고)

이 과정이 귀찮으면 ABcount, CDcount를 long으로 선언해줘도 상관없음. 

 

5) 이 문제를 통해 얻어갈 것

투 포인터(two pointer) 활용.

이진탐색을 통해서도 문제풀이가 가능할 것 같다.

4개의 배열을 2개의 배열로 줄이는 것은 애드혹(adhoc)적인 요소가 필요하다.

 

C++ 코드 : 

// 합이 0인 네 정수 7453 C++
#if 1
#pragma warning(disable:4996)
#include <cstdio>
#include <vector>
#include <algorithm>

#define MAX (4000 + 1)

using namespace std;

int N;					// 숫자 개수
long long ans;			// ans : 정답

int A[MAX];
int B[MAX];
int C[MAX];
int D[MAX];

int AB[MAX * MAX];		//입력받은 배열 2개의 합
int CD[MAX * MAX];		//입력받은 배열 2개의 합

int ABpt, CDpt;		// 투포인터를 위한 포인터

void input();

void makeSumArray();

int main() {
	// 1. 입력받는다
	//freopen("input.txt", "r", stdin);
	input();

	// 2. 배열 2개씩 짝지어서 합 배열 만들기
	makeSumArray();
	
	// 3. 오름차순으로 2가지 배열 정렬
	sort(AB, AB + ABpt);
	sort(CD, CD + ABpt);

	// 4. 투포인터
	CDpt = ABpt - 1;	// 둘의 수가 같으므로 CD 포인터 = AB 포인터 - 1
	for (int i = 0; i < ABpt && CDpt >= 0; ) {
		int ABsum = AB[i];
		int CDsum = CD[CDpt];
		int ABcnt = 0;
		int CDcnt = 0;
		int totSum = ABsum + CDsum;
		// 4-1. 합이 0인 경우(답인경우)
		if (totSum == 0) {
			// 4-1-1. AB에서 중복인 답의 개수를 체크
			while (i < ABpt && ABsum == AB[i]) {
				i++;
				ABcnt++;
			}
			// 4-1-2. CD에서 중복인 답의 개수를 체크
			while (CDpt >= 0 && CDsum == CD[CDpt]) {
				CDpt--;
				CDcnt++;
			}
			// 4-1-3. AB count * CD count
			ans += (long long)ABcnt * (long long)CDcnt;
		}
		// 4-2. 0보다 클 경우 값을 줄여야하므로 CD의 포인터를 낮추기
		else if (totSum > 0) {
			CDpt--;
		}
		// 4-3. 0보다 작을 경우 값을 늘려야하므로 AB의 포인터를 낮추기
		else {
			i++;
		}
	}

	printf("%lld", ans);

	return 0;
}

void input() {
	scanf("%d", &N);
	
	for (int i = 0; i < N; i++) {
		scanf("%d %d %d %d", &A[i], &B[i], &C[i], &D[i]);
	}

}

// 2. 배열 2개씩 짝지어서 합 배열 만들기
void makeSumArray() {
	ABpt = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			AB[ABpt] = A[i] + B[j];
			CD[ABpt] = C[i] + D[j];
			ABpt++;
		}
	}
}
#endif

 

Java 코드 : 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

// 합이 0인 네 정수 백준 7453
public class Main {
	
	static int N;			// N 숫자 개수
	static long ans;		// ans 답
	static int[] A,B,C,D;		// 입력받은 배열
	static int[] AB, CD;		// 입력받은 배열 2개의 합
	static int ABid, CDid;	// 투포인터를 위한 포인터
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		// N 입력
		N = Integer.parseInt(br.readLine());
		
		// 초기값 세팅
		A = new int[N];
		B = new int[N];
		C = new int[N];
		D = new int[N];
		AB = new int[N*N];
		CD = new int[N*N];
		ans = 0;
		
		// 1. 주어진 배열 입력받기
		for (int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			A[i] = Integer.parseInt(st.nextToken());
			B[i] = Integer.parseInt(st.nextToken());
			C[i] = Integer.parseInt(st.nextToken());
			D[i] = Integer.parseInt(st.nextToken());
		}
		
		// 2. 배열 2개씩 짝지어서 합 배열 만들기
		ABid = 0;
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				AB[ABid] = A[i]+B[j];
				CD[ABid] = C[i]+D[j];
				ABid++;
			}
		}
		CDid = ABid-1;	// 둘의 수가 같으므로 CD 포인터 = AB 포인터 - 1
		
		// 3. 오름차순으로 2가지 배열 정리
		Arrays.sort(AB);
		Arrays.sort(CD);
		
		// 4. 투포인터
		for (int i=0; i<ABid && CDid>=0; ) {
            int ABsum = AB[i];
            int CDsum = CD[CDid];
            int ABcnt = 0;
            int CDcnt = 0;
            int totSum = ABsum+CDsum;
            // 4-1. 합이 0인 경우(답인경우)
            if(totSum == 0) {
            	// 4-1-1. AB에서 중복인 답의 개수를 체크
                while(i<ABid && ABsum == AB[i]) {
                    i++;
                    ABcnt++;
                }
                // 4-1-2. CD에서 중복인 답의 개수를 체크
                while(CDid>=0 && CDsum == CD[CDid]) {
                    CDid--;
                    CDcnt++;
                }
                // 4-1-3. AB count * CD count
                ans+=(long)ABcnt*(long)CDcnt;
            }
            // 4-2. 0보다 클 경우 값을 줄여야하므로 CD의 포인터를 낮추기
            else if(totSum >0) {
                CDid--;
            }
            // 4-3. 0보다 작을 경우 값을 늘려야하므로 AB의 포인터를 낮추기
            else {
                i++;
            }
		}
		
		// 정답 출력
		bw.write(String.valueOf(ans)+"\n");				

		bw.flush();
		bw.close();
		br.close();
	}
}