합이 0인 네 정수(백준_7453번)

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

7453번: 합이 0인 네 정수

문제 설명

입력값

4
-5 1 -3 2
-9 5 -8 7
2 2 -11 -6
3 7 4 -1

 

 

 

A, B, C, D중 하나씩 골라서 총 합이 0이 되는 조합의 수를 구하여라!!

 

문제에 대한 아이디어 및 구현

시간제한과 메모리

시간제한이 12초 메모리 제한이 1024MB라는 점에서 처음에는 어떻게든 답을 구하면 되겠다고 생각했다.

근데 생각해보니 A B C D의 갯수의 최대가 4000개이다. 모든 배열에서 하나씩 뽑아서 더한다면 경우의 수는 4000 * 4000 * 4000 * 4000이다. 아무리 12초라도 시간 초과가 걸릴 것 이다. 다른 방법이 필요해 보인다.

 

시간을 줄이기 위한 아이디어

4개의 수를 더하는 경우는 무조건 시간 초과가 걸릴 거 같다.

배열에서 조건을 만족하는 합의 갯수를 구하는 방법 중 가장 유명한 방법은 투 포인터이다.  

그러므로 4개의 수가 아닌 2개의 수를 더하는 것으로 생각한 뒤 투 포인터를 이동시키면 더 빨리 탐색할 수 있겠다고 생각했다. 즉, A+B+C+D 가 아닌 (A+B) + (C+D)로 생각하는 것이다.

 

이차원 배열 변경 구현

int sum[][] = new int[2][n*n];
int index =0;
for(int i=0; i<n; ++i){
    for(int j=0; j<n; ++j) {
        sum[0][index] = arr[i][0] + arr[j][1];
        sum[1][index] = arr[i][2] + arr[j][3];
        ++index;
    }
}

위의 문제에서 입력 받은 2차원 배열을 위의 그림 처럼 합의 2차원 배열로 변경해준다. 그리고 각 배열을 sort해준다.

• Sort 할 때 시간 복잡도는 O(nLonn) 이므로 n이 최대 16000000이므로 시간제한안에 sort할 수 있다. 

이제 여기서 A+B는 앞에서부터 C+D는 뒤에서부터 탐색을 하면서 0과 일치하는지 검사하면 된다.

Arrays.sort(sum[0]);
Arrays.sort(sum[1]);

 

투 포인터 탐색 구현

int start = 0; //A+B 배열의 index
int end = n*n-1; //C+D 배열의 index
long answer =0;
while(true){
    int now = sum[0][start] + sum[1][end];
    if(now == 0) {
        start++;
        end--;
        answer++;
    }
    if(now > 0) end--;
    else start++;
    if(start >= n*n || end < 0) break;
}

• now가 0이면 start는 하나 뒤로 end는 하나 앞으로 보낸다.
• now가 0보다 크면 end를 하나 앞으로 간다.
• now가 0보다 작으면 start를 하나 뒤로 간다. 

틀린 이유

• A+B 에서 9, C+D에서 -9인 지점을 보면 위의 코드 대로한다면 만난 뒤 바로 A+B = 10, C+D= -9인 부분으로 넘어가게 된다.
• 원래는 9와 -9의 합으로 answer에 3개가 더해 져야 한다. 위의 코드는 1개만 더해지고 끝난다.

int start = 0; //A+B 배열의 index
int end = n*n-1; //C+D 배열의 index
long answer =0;
while(true){
    int now = sum[0][start] + sum[1][end];
    int startCnt=1;
    int secondCnt=1;
    if(now == 0) {
        while(start <= (n*n)-2 && sum[0][start] == sum[0][start+1]){
            ++start;
            ++startCnt;
        }
        while(0 < end && sum[1][end] == sum[1][end-1]){
            --end;
            ++secondCnt;
        }
        answer += (long) startCnt*secondCnt;
    }
    if(now > 0) end--;
    else start++;
    if(start >= n*n || end < 0) break;
}

• now가 0일 때 start가 A+B 배열의 index의 맨 마지막이 아니고 지금 index와 다음 index의 값이 같다면 같은 수가 몇개있는지 세준다.
• now가 0일 때 end가 C+D 배열의 index의 맨 앞 부분이 아니면 지금 index와 다음 index의 값이 같다면 같은 수가 몇개있는지 세준다.
• answer에 두 수를 곱한 수를 더한다. (여기서 곱한 이유는 startCnt가 2개 secondCnt가 3개 이면 이 숫자들은 각각 다른거기 때문에 0을 만들 수 있는 조합의 수는 총 6가지이기 때문이다)

 

전체 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(buf.readLine());
        int n = Integer.parseInt(st.nextToken());
        int arr[][] = new int[n][4];
        for(int i=0; i<n; ++i){
            st = new StringTokenizer(buf.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
            arr[i][2] = Integer.parseInt(st.nextToken());
            arr[i][3] = Integer.parseInt(st.nextToken());
        }
        int sum[][] = new int[2][n*n];
        int index =0;
        for(int i=0; i<n; ++i){
            for(int j=0; j<n; ++j) {
                sum[0][index] = arr[i][0] + arr[j][1];
                sum[1][index] = arr[i][2] + arr[j][3];
                ++index;
            }
        }
        Arrays.sort(sum[0]);
        Arrays.sort(sum[1]);
        int start =0; int end = n*n-1;
        long answer =0;
        while(true){
            int now = sum[0][start] + sum[1][end];
            int startCnt=1;
            int secondCnt=1;
            if(now == 0) {
                while(start <= (n*n)-2 && sum[0][start] == sum[0][start+1]){
                    ++start;
                    ++startCnt;
                }
                while(0 < end && sum[1][end] == sum[1][end-1]){
                    --end;
                    ++secondCnt;
                }
                answer += (long) startCnt*secondCnt;
            }
            if(now > 0) end--;
            else start++;
            if(start >= n*n || end < 0) break;
        }
        System.out.println(answer);
    }
}

https://github.com/Heron-Woong/CodingTest_Practice/commit/d7aa52e7092f656f6828c79481cc32d01e36ec93

백준_7453, 합이 0인 네 정수 · Heron-Woong/CodingTest_Practice@d7aa52e