[C/C++] 백준 #3013 부분 수열의 중앙값(누적 합)

문제를 푼지는 꽤 되었는데, 지금에 작성하라고 한다면, 이진검색을 사용하지 않고, t 값에 대한 테이블값을 별도로 만들어서 저장하는 방식을 택했을 듯 합니다.  데이터의 전체 갯수가 100,000이니까, 누적합 테이블을 만들 때에는 200,000개 정도의 추가 공간을 만들면 됩니다.  그러면 정렬 후 이진 검색하는 시간 비용을 줄일 수 있습니다.  정렬 시간 복잡도는 \(O(N \log N)\)이고, 이진검색하는 비용도 \(O(N \log N)\)이 되니까요.

 

accumulated sum

 

문제는 다음 링크에 있습니다.

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

 

이 문제는 주어진 배열에서 특정 값 b를 기준으로 좌우의 수들을 분석하고, 이 기준을 중심으로 하는 부분 배열의 개수를 세는 문제입니다. 우선 문제의 흐름과 알고리즘을 하나씩 분석해보겠습니다.

1. 입력받기

scanf("%d%d",&n,&b);
for(i=0;i<n;i++) { scanf("%d",v+i); if(v[i]==b) k=i; }

위 코드는 배열의 크기 n과 기준값 b를 입력받고, 배열 v의 값을 차례로 저장하면서 b가 등장하는 위치 k를 저장합니다. 이 k 값이 기준값 b가 위치한 인덱스가 됩니다. 이 인덱스 기준으로 왼쪽과 오른쪽 부분 배열을 구분해서 분석할 예정입니다.

2. 기준값 왼쪽 분석

for(i=k-1,t=0;i>=0;i--) 
    v[i]=(v[i]>b)?++t:--t, r+=v[i]?0:1;

이 루프는 b보다 작은 값과 큰 값을 구분하여 b보다 큰 값이면 t를 증가시키고, 작은 값이면 t를 감소시킵니다. 또한, v[i]가 0이 되는 경우는 그 시점까지 b와 비교한 값들이 정확히 균형을 이루는 부분 배열을 나타내므로, 결과값 r에 1을 더합니다.

3. 정렬 및 오른쪽 분석

std::sort(v,v+k);
for(i=k+1,t=0;i<n;i++)
{
    t+=(v[i]>b)?-1:1;
    r+=!t;
    r+=std::distance(v,std::upper_bound(v,v+k,t));
    r-=std::distance(v,std::lower_bound(v,v+k,t));
}

먼저 기준값 k 이전의 배열을 오름차순으로 정렬합니다. 그런 다음, b의 오른쪽 부분을 같은 방식으로 분석하는데, 이때는 t 값을 점진적으로 업데이트하며, 중앙을 기준으로 좌우가 균형을 이루는 경우를 찾습니다.

정렬된 배열에서 t 값과 일치하는 값들이 얼마나 되는지 확인하기 위해 std::upper_bound와 std::lower_bound 함수를 사용합니다. 이는 좌우 균형을 이루는 부분 배열의 개수를 세기 위한 방식입니다.

4. 출력

마지막으로, 계산된 결과값 r을 출력합니다.

printf("%d\n", r);

이 코드가 출력하는 값은 b를 기준으로 좌우에 균형을 이루는 부분 배열의 개수입니다.

---

핵심 정리

이 문제는 특정 기준값을 중심으로 한 배열에서 좌우 균형을 이루는 부분 배열의 개수를 세는 문제입니다. 주요 알고리즘은 기준값을 기준으로 좌우를 나누고, 좌우 각각에서 값을 증가 또는 감소시키면서 그 값들이 얼마나 균형을 이루는지를 확인하는 방식입니다. 최적화를 위해 정렬과 이진 탐색을 활용하여 빠르게 답을 구하는 방법을 사용하였습니다.

이 코드는 배열 크기가 최대 100,000이므로 시간 복잡도를 고려해 O(n log n) 정도의 알고리즘을 사용하여 효율적으로 문제를 해결하고 있습니다.

 

전체 소스는 다음과 같습니다.

//----------------------------------------------------------
//    baekjoon #3013 - SREDNJI
//        - by Aubrey Choi
//        - created at 2020-01-31
//----------------------------------------------------------
#include <stdio.h>
#include <algorithm>

int main()
{
    int n, b, v[100000], t, i, s, k, r=1;
    scanf("%d%d",&n,&b);
    for(i=0;i<n;i++) { scanf("%d",v+i); if(v[i]==b) k=i; }
    for(i=k-1,t=0;i>=0;i--) v[i]=(v[i]>b)?++t:--t,r+=v[i]?0:1;
    std::sort(v,v+k);
    for(i=k+1,t=0;i<n;i++)
    {
        t+=(v[i]>b)?-1:1;
        r+=!t;
        r+=std::distance(v,std::upper_bound(v,v+k,t));
        r-=std::distance(v,std::lower_bound(v,v+k,t));
    }
    printf("%d\n", r);
}