[Algorithm]Baekjoon 2143번 : 두 배열의 합

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

2143번: 두 배열의 합

 
 
using namespace std;
 
int t, n, m;
long long answer = 0;
int arrN[1001] = { 0 };
int arrM[1001] = { 0 };
map<int, int> check;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> t;
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> arrN[i];
    }
 
    for (int i = 0; i < n; ++i)
    {
        int sum = 0;
 
        for (int j = i; j < n; ++j)
        {
            sum += arrN[j];
            ++check[sum];
        }
    }
 
    cin >> m;
 
    for (int i = 0; i < m; ++i)
    {
        cin >> arrM[i];
    }
 
    for (int i = 0; i < m; ++i)
    {
        int sum = 0;
 
        for (int j = i; j < m; ++j)
        {
            sum += arrM[j];
            answer += check[t - sum];
        }
    }
    
    cout << answer;
}
 
 
 
 

 

두 수열 A,B에 대해 각각 부분수열의 합을 모두 구한 후, 타겟T를 만들 수 있는 쌍의 개수를 구하는 문제이다.

일단은 단순하게 풀었다. 부분수열합의 경우의 수를 모두 구해서 map에다가 카운팅을 했다. (특정수가 몇개나왔는지 map에다가 기록해놨다는 말.)

물론,  '가능하면' map같은거말고 그냥 배열에다가 하는게 속도가 월등히 빠르다. 하지만 이 문제같은경우는 최대숫자가 10억까지 나오기 때문에 메모리제한에 걸릴 뿐더러, 음수도 존재하기 때문이다.

물론 절대값이 작다면 음수여도 offset값을 더해서 양수로 매핑하면 되긴한다. 일종의 테크닉인데, 최근에 관련해서 푼 문제가 있다. (Meet in the Middle문제)

 

어쨌든 A수열의 가짓수들을 맵에다가 기록 후, B의 가짓수들을 구할 때마다 t - B의 가짓수값이 vA의 부분수열합에 존재한다면, 그만큼 answer에 누적시켰다.

제출은 통과됐지만 400대ms가 나왔다. map을 통한 접근이 시간이 꽤 걸린다는 것이다.

참고로 그냥 map(바이너리)은 400대ms가 나왔고, 해쉬맵인 unordered_map은 200대ms가 나왔다.

 

이후 좀 더 빠른 속도를 위해 다른사람의 풀이를 보고 다시 코드를 작성해봤다.

 

 
 
using namespace std;
 
int t, n, m;
int arrA[1001] = { 0 };
int arrB[1001] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> t;
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> arrA[i];
    }
 
    vector<int> vA;
    for (int i = 0; i < n; ++i)
    {
        int sum = 0;
 
        for (int j = i; j < n; ++j)
        {
            sum += arrA[j];
            vA.push_back(sum);
        }
    }
    sort(vA.begin(), vA.end());
 
    cin >> m;
 
    for (int i = 0; i < m; ++i)
    {
        cin >> arrB[i];
    }
 
    vector<int> vB;
    for (int i = 0; i < m; ++i)
    {
        int sum = 0;
 
        for (int j = i; j < m; ++j)
        {
            sum += arrB[j];
            vB.push_back(sum);
        }
    }
    sort(vB.begin(), vB.end());
 
    long long answer = 0;
    for (int i = 0; i < vA.size(); ++i)
    {
        int targetNum = t - vA[i];
        int targetNumCount = upper_bound(vB.begin(), vB.end(), targetNum) - lower_bound(vB.begin(), vB.end(), targetNum);
 
        answer += targetNumCount;
    }
 
    cout << answer;
}
 
 
 
 
 

 

맨 처음코드는 특정수가 몇개나왔는지 먼저 카운팅했던 것과 달리, 이 코드는 일단 중복된 숫자여도 모두 구해서 벡터에 저장해놓는다. vA에는 수열A의 부분수열의 합들이 들어있고 vB에는 수열B의 부분수열의 합들이 들어있다.

만약 타겟숫자인 T가 5라면, vA의 원소 하나가 1일 때 vB에서 T-vA[i], 즉 5 - 1인 '4의 개수'를 vB에서 찾아주는 것이다.

 

여기서 '특정숫자'의 '개수'를 효율적으로 찾는것이 관건이다.

단순히 N번반복해서 찾을 수도 있겠지만, 당연히 효율적이지 못하다. 여기서 왜 효율적이지 못하냐? 더 효율적인 방법이 존재하기 때문에 그렇다.

 

결론적으로 upper_bound와 lower_bound를 통해 구할 수 있다.

upper_bound는 특정숫자를 초과하는 숫자의 인덱스를 반환하고, lower_bound는 특정숫자의 '이상'인 숫자의 인덱스를 반환하다.

그렇기 때문에 upper_bound의 결과값 iterator에서 lower_bound 결과값 iterator를 빼면 '특정숫자의 개수'를 구할 수 있다.

단, upper_bound와 lower_bound는 사용전에 해당 컨테이너가 반드시 정렬이 되어있어야 한다.

시간복잡도는 각각 logN이고 vA의 크기만큼하기 때문에 vA의 크기 * 2(lower한번, upper한번) * logN 이 된다. 

 

그래서 위 코드를 제출했을 때 대략 90ms대가 나왔다. 기존에 unordered_map으로 카운팅했을 때, 200ms가 나왔던거에 비하면 시간효율이 굉장히 좋아졌다.

그리고 사실, 위 코드에 보면 upper,lower_bound를 수행하는 vB말고 vA도 정렬시킨걸 확인할 수 있는데, 사실 로직상 vA는 정렬 안시켜도 된다. 위 로직은 어차피 vA원소 하나씩 접근해서 수행하니까.

 

근데 놀랍게도.. vA를 정렬시킨 위의 코드는 90ms대가 나오고, 정렬 안시키고 제출하면 120ms대가 나온다. 

단순 생각해보면, N logN의 시간복잡도를 가진 sort를 수행안한 vB가 더 적게 나와야하는게 맞을텐데 말이다.

일단 당장의 뇌피셜론, 캐쉬의 지역성때문인가? 하는 생각이 든다.

정렬시켜놓으면 같은 숫자가 연속되니, lower_bound와 upper_bound의 값들이 캐쉬에 저장되어져있다가 바로 꺼내서 쓰니 더 빠른게 아닌가.. 싶다.

 

그리고 거의 유사한개념으로, 사실 좀 더 최적화 여지가 있다. 애초에 vA도 정렬시켜놓으면 같은숫자가 연속되니까 그냥 특정숫자가 몇개나 연속되는지 체크 후, 곱연산 해버리면 된다. 

위의 코드정도로도 코테에서 시간초과로 떨어질일은 절대없을거같긴한데, 얼마나 더 최적화될지 궁금해서 코드로 작성해봤다.

 

 
using namespace std;
 
int t, n, m;
int arrA[1001] = { 0 };
int arrB[1001] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> t;
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> arrA[i];
    }
 
    vector<int> vA;
    for (int i = 0; i < n; ++i)
    {
        int sum = 0;
 
        for (int j = i; j < n; ++j)
        {
            sum += arrA[j];
            vA.push_back(sum);
        }
    }
    sort(vA.begin(), vA.end());
 
    cin >> m;
 
    for (int i = 0; i < m; ++i)
    {
        cin >> arrB[i];
    }
 
    vector<int> vB;
    for (int i = 0; i < m; ++i)
    {
        int sum = 0;
 
        for (int j = i; j < m; ++j)
        {
            sum += arrB[j];
            vB.push_back(sum);
        }
    }
    sort(vB.begin(), vB.end());
 
    long long answer = 0;
 
    int index = 0;
 
    while (index < vA.size())
    {
        int num = vA[index];
        int targetNum = t - vA[index];
        int targetNumCount = upper_bound(vB.begin(), vB.end(), targetNum) - lower_bound(vB.begin(), vB.end(), targetNum);
        
        int count = 1;
        ++index;
        while (index < vA.size() && vA[index] == num)
        {
            ++index;
            ++count;
        }
 
        answer += (long long)count * targetNumCount;
 
   }
    cout << answer;
}
 
 
 
 
 

 

위 코드는 88ms로, 바로 직전코드가 92ms가 나왔던것을 감안하면 사실 거의 차이는 없다.

참고로, 출력시킬 정수형 변수의 데이터타입은 int로 하면 안된다. 

수열A의 부분집합개수 * 수열B의 부분집합개수 => int의 범위를 벗어날만큼 많기 때문이다.