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

백준의 합이 0인 네 정수(7453) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 먼저 이 문제를 해결하는 가장 쉬운 방법은 4중 for문을 통해서 하나하나 모든 원소를 다 체크하면서 계산을 해주면

   정답은 도출할 수 있다. 하지만 ! 최악의 경우 4000개 크기의 배열이 4개 주어졌을 경우, 총 4000^4번 체크를 해줘야 하고

   이는 제한시간인 2초내에 해결될 수 없는 양이다.

  

   본인은 이 시간초과를 해결하기 위해서 배열을 2개로 만들어주었다. 1,2,3,4번 이렇게 4개의 배열이 있다고 가정하면

   1번배열과 2번 배열을 합쳐서 나올 수 있는 원소들을 저장하는 배열 하나와, 3번배열과 4번 배열을 합쳐서 나올 수 있는

   배열 하나 이렇게 해서 2개의 배열을 만들어 주었다.

   이 후, 이 배열들을 오름차순으로 정렬을 시켜 주었다.

   여기서 부터 1번배열과 2번배열을 합친 배열을 'A배열' , 3번배열과 4번 배열을 합친 배열을 'B배열' 이라고 표기하겠다.

   지금 정렬을 해주었기 때문에 A배열과 B배열 모두 0번 Index에는 가장 작은값이, 마지막 Index에는 가장 큰값이

   저장되어 있을 것이다.

   합이 0이 되기 위해서는 작은 값과 큰 값이 만나야 한다. 따라서, A배열은 첫번째 Index부터, B배열은 마지막 Index부터

   탐색을 시작해주었다.

   탐색을 하면서 모든 값을 값을 체크해주는 것이다.

   이렇게 되면 최악의 경우 1600만개짜리 배열 2번을 탐색하게된다.

2) 그렇다면 지금부터는 탐색을 하면서 고려해줘야 될 부분에 대해서 알아보자.

   1. A배열 + B배열이 0이라면 ??

   - 문제에서 원소가 중복되지 않는 다는 말은 없다. 즉, 현재 A배열의 원소가 'a'이고 B배열의 원소가 'b' 라고 쳤을 때

     A배열의 그 다음 원소가 'a'일수도 있는 것이다. B배열의 그 다음 원소가 'b'인 경우가 있을수도 있고

     즉, 그림으로 나타내면 다음과 같은 경우가 존재한다는 것이다.

  

     위와 같은 경우, 현재 원소들끼리 더했을 때 -3 + 3 으로 0이 나오게 된다. 하지만 그 다음 원소를 보더라도 똑같이

     -3 + 3 으로 0이 나오게 된다. 그럼 총 '-3 + 3' 이 몇개가 있을까? 총 6개이다.

     '6'이라는 결과값이 어떻게 나왔는지 계산해보면, A배열에서 '-3'의 갯수와, B배열에서의 '3'의 갯수를 곱해주면 된다.

     정리를 해보자.. 현재 A배열 + B배열이 0인 경우, A배열에서의 현재 원소의 총 갯수 * B배열에서의 현재 원소의 총 갯수를

     해주면 0이 되는 경우를 찾을 수 있다는 것이다.

   2. A배열 + B배열이 < 0 이라면 ?

   - 만약 2개를 더했을 때 0보다 작다는 것은 무슨 의미일까?? A배열의 데이터 값이 너무 작다는 것을 의미한다.

     즉, A배열의 Index만 다음으로 넘겨주면 된다.

   3. A배열 + B배열이 > 0 이라면 ?

   - 2개를 더했을 때 0보다 크다는 것은 B배열의 데이터가 너무 크다는 것을 의미한다. 즉, 이때는 B배열의 Index만

     다음으로 넘겨주면 된다.

그리고 마지막으로 주의해야 할 것은 0이 되는 경우가 최악의 경우 int형의 범위를 넘는다는 것이다.

따라서, int형이 아닌 long long과 같이 자료형의 변환이 필요하다 !

[ 지금부터는 이 문제에 대한 이야기를 별도로 하겠습니다. 아래의 글을 읽기 전에 가장 아래 소스코드를 먼저

  참고해주시면 감사하겠습니다. ]

결론부터 말씀드리자면 제가 아래에서 소개할 코드는 사실 본인도 왜 통과가 된 코드인지 잘 모르겠고, 또한 정말 좋고

효율성이 뛰어난 올바른 코드라고는 말씀을 드리지 못할 것 같습니다. 오히려 잘못된 코드인 것 같습니다.

기존의 저의 글이 저의 잘못된 계산으로 인해서 'A배열'과 'B배열'이 16만개라고 표현되어 있었습니다.

저는 16만개로 계산을 했고, 그에 따른 풀이를 포스팅했는데 많은 분들께서 잘못되었다고 말씀해주심과 동시에

왜 이 코드가 TLE를 면할 수 있는지 물어보셔서 다시한번 문제를 보게 되었습니다.

최악의 경우 4000개 일 경우, 크기가 1600만인 'A배열'과 'B배열'이 생성됩니다.

그렇게 되면, sort함수를 A배열에서 한번, B배열에서 한번 총 2번을 하게 되는데, 정렬하는데 걸리는

시간복잡도를 어림잡아 계산해보면 1600만 x log(1600만) 이 됩니다.

계산기로 계산해본 결과 log(1600만) = 23.xxxx 라는 값이 나오게 됩니다.

즉, 1600만 x 약 24 를 하게 되면 약 3억이 조금 넘는 값이 나오게 됩니다.

다시 말해서 4개의 배열을 합쳐서 2개의 배열을 만들게 되면, 최악의 경우 크기가 1600만인 배열이 생성되어지고

크기가 1600만인 배열을 STL에서 제공하는 sort함수를 사용해서 연산할 경우 약 3억이 넘는 연산을 하게 됩니다.

그럼 결과적으로 sort함수를 2번 사용하니까 약 3억이 넘는 연산을 2번한다는 이야기이고, 약 6억 ~ 7억 사이의 연산을

하게됩니다.

보통 알고리즘 문제에 접근할 때, '컴퓨터는 1초에 1억번의 연산을 할 수 있다' 라고 생각을 하고 접근하게 됩니다.

즉, 위에서 말한 6억 ~ 7억 사이의 연산을 하기 위해서는 6초 이상의 시간이 걸린다고 볼 수 있습니다.

하지만 이 문제의 제한시간은 2초이고 이렇게 계산했을 때 절대로 PASS를 받을 수 없는 코드라고 생각합니다.

하지만 아래의 코드를 제출하게되면 '976ms'로 1초도 되지 않은 시간이 걸린채로 PASS를 받을 수 있습니다.

이 쯤에서 다시 한번 말씀드리지만 애초에 제가 '1600만'이 아닌 '16만'으로 계산을 해서 문제를 해결했고, '16만'을 기준으로

풀이를 올렸습니다. 저의 잘못된 계산으로 이 글을 읽으신 분들에게 혼란을 드린점은 정말 죄송하다고 전하고 싶습니다.

그럼 다시 본론으로 돌아와서, 어떻게 6억 ~ 7억번 사이의 연산을 하는데 왜 pass를 받는지에 대해서 이야기해보겠습니다.

위에서 말씀드렸듯이 제가 계산을 했을 때도 약 6억 ~ 7억번 사이의 연산을 하는데 왜 TLE가 발생하지 않는지

잘 모르겠습니다.

여럿 지인들에게 이부분에 대해서 물어봤더니, 2가지 부분에서 굉장히 단순한 생각을 하고 있다고 말해주었습니다.

첫 번째는 '1초에 1억번의 연산을 한다. 그러므로 2초에는 2억번의 연산을 할 수 있다.' 라는 부분입니다.

컴퓨터의 성능에 따라서 1초에 5억번도 10억번도 연산이 가능하다고 합니다. 1초에 1억번이라는 것은 굉장히 단순한

생각일 수 있다 라는 것이였습니다. 그렇기 때문에 계산을 했을 때 2억번이 넘는다고 해서 무조건 2초내로 해결이 되지

않는다 라는 것은 굉장히 단순한 생각일 수 있다는 것입니다. 또한, 1초에 1억번 연산을 한다 라고 했을 때, 그 한번 한번의

무게에 따라서도 다르다고 합니다. 굉장히 가벼운 연산에 대해서는 더 많은 연산을, 무거운 연산에 대해서는 상대적으로

더 적은 연산을 한다는 것입니다. 가장 단순하고 보편적으로 생각했을 때 1초에 1억번 연산이 가능하다 라고 표현하는 것입니다.

두 번째는 'STL에서 제공해주는 sort함수는 NlogN 만큼의 시간복잡도를 갖는다.' 라는 부분입니다. sort함수는 내부적으로

여러개의 정렬함수가 합쳐진 형태로 존재한다고 합니다. 우리가 알고 있는 퀵정렬, 병합정렬, 힙정렬, 삽입정렬 이렇게 딱 정해져 있는 정렬 방식이 아닌, 들어오는 데이터의 크기와 상태에 따라서 적절한 정렬법들이 섞인채로 정렬이 작동된다고 합니다.

따라서, sort함수가 무조건적으로 NlogN의 복잡도를 갖고 그 만큼의 연산을 한다고 계산하는 것이 실제 프로그램에서 그만큼의

연산을 한다고 단정짓지는 못한다는 것입니다.

하지만 ! 정말 위에서 한 이야기처럼 1초에 1억번이 넘는 연산을 하는 컴퓨터에서, 이 문제의 연산은 상대적으로 가벼운 연산이기 떄문에 더 많은 연산을 할 수 있다라고 가정 하고, sort함수가 NlogN보다 훨씬 더 빠른 시간복잡도를 갖는다고 하더라도, 저처럼 알고리즘 문제를 푸는 사람 입장에서 "이 문제는 시간제한이 2초인데, 컴퓨터의 사양을 믿고 6억번이 넘는 연산을 하는

코드를 제출해봐야지 !" 라고 할 수는 없는 격입니다. 절대로 그럴 수가 없습니다.

이런 부분 때문에 제가 아래에 올린 코드가 PASS를 받을 수는 있지만, 올바르고 정확하고 효율적인 풀이라고는 할 수 없을 것

같습니다. 그렇다고 문제를 푸는 사람에게 "컴퓨터의 사양을 믿어봐!" 혹은 "내부 sort함수는 우리가 생각하는 NlogN 보다 더 빠르게 정렬이 가능할거야 !" 라고 말을 할 수는 없습니다.

따라서, 아래의 코드는 제 코드이지만, 굉장히 비효율적이고 알고리즘 문제를 푸는 사람 입장에서는 이해할 수 없는

시간복잡도를 갖는데도 불구하고 TLE가 발생하지 않는 코드입니다. 더 나아가서는 본인조차도 왜 TLE가 발생하지 않는지

이해하기 힘든 코드입니다.

이 부분에 대해서 계속해서 찾아보고 공부를 하다가 백준사이트의 블로그에서 아래와 같은 글을 찾았습니다.

[ sort함수 언어 별 정렬속도 비교 ]

위의 글을 읽어보시면, C++에서 크기가 1천만 짜리 배열을 sort하게 되면 약 775ms가 걸린다고 되어있습니다.

이 문제는 1천6백만 짜리 배열이기 때문에 정말 대략적으로 계산을 해서 800ms가 걸린다고 생각해보면,

아래의 코드가 어쩌면 TLE가 발생하지 않고 PASS를 받을 수도 있다고 생각합니다.

배열을 합치는데 1600만번의 연산 = 약 160ms

A배열에 대한 sort함수 한번 = 800ms

B배열에 대한 sort함수 두번 = 800ms

원소의 갯수를 찾는 while문 과정에서의 연산 = 약  160ms

모두 더하면 제한시간 2초 내에 가능한 시간이긴 합니다. 

마지막으로 정리하겠습니다.

아래의 코드는 정말 비효율적이고 알고리즘을 푸는 사람 입장에서는 제한시간에 비해서 훨씬 더 많은 시간복잡도를 갖는

코드임에도 불구하고 제한시간 내에 통과가 가능합니다. 통과가 되는 정확한 이유를 본인 또한 잘 모르겠습니다.

그나마 통과가 되는 이유를 억지로라도 한번 찾아보자면 위에서 말했던 단순히 생각했던 2가지 부분 때문이였고

그 부분에 대해서 위에서 링크를 걸어놓은 sort함수 정렬 속도로 대략적으로 계산을 했더니 2초내에 되긴 됬습니다.

하지만 ! 그렇다고 해서 알고리즘 문제를 푸는 사람으로써 저렇게 계산을 하고 아래와 같이 코드를 구현했다 라고 하기에는

조금 부족한 부분이 있는 것 같습니다.

[ 소스코드 ]

#include<iostream>
#include<algorithm>
 
#define endl "\n"
#define MAX 4000
typedef long long ll;
using namespace std;
 
int N;
ll Answer;
int Arr[4][MAX], AB[MAX * MAX], CD[MAX * MAX];
 
void Input()
{
    cin >> N;
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < 4; j++)
        {
            cin >> Arr[j][i];
        }
    }
}
 
void Solution()
{
    int Idx = 0;
    /*=================================================================
       4개의 배열을 2개의 배열로 만들어주는 과정
       : AB[] = 0번 배열과 1번 배열을 합쳤을 때 나올 수 있는 원소를 저장
       : CD[] = 2번 배열과 3번 배열을 합쳤을 때 나올 수 있는 원소를 저장 
    =================================================================*/
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            AB[Idx] = Arr[0][i] + Arr[1][j];
            CD[Idx] = Arr[2][i] + Arr[3][j];
            Idx++;
        }
    }
 
    /* 2개의 배열을 정렬 */
    sort(AB, AB + Idx);
    sort(CD, CD + Idx);
 
    int AB_Idx = 0;            // A배열은 0번 Index부터 (처음부터)
    int CD_Idx = Idx - 1;    // B배열은 마지막 Index부터 (마지막부터)
 
    while (AB_Idx < Idx && CD_Idx >= 0)        // 어느 한 곳이라도 모두 탐색하면 종료
    {
        if (AB[AB_Idx] + CD[CD_Idx] == 0)    // A배열 + B배열 = 0 인 경우
        {
            int Orig = AB_Idx;
            ll Same_AB = 0, Same_CD = 0;
 
            while (AB[AB_Idx] + CD[CD_Idx] == 0)
            {
                /* A배열에서 현재 원소와 같은 원소의 갯수를 Count해준다.*/
                if (AB_Idx >= Idx) break;
                Same_AB++;
                AB_Idx++;
            }
 
            while (AB[Orig] + CD[CD_Idx] == 0)
            {
                /* B배열에서 현재 원소와 같은 원소의 개수를 Count해준다.*/
                if (CD_Idx < 0) break;
                Same_CD++;
                CD_Idx--;
            }
            
            Answer = Answer + (Same_AB * Same_CD);    // 곱한 값을 전체 결과값에 + 
        }
        else if (AB[AB_Idx] + CD[CD_Idx] < 0) AB_Idx++;
        else CD_Idx--;
    }
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}