[BaekJoon/백준] 10816번 C++

문제는 두 가지 방법으로 풀었다.

---

 

감이 왔다가, 다시 헷갈렸다가... 조금 헤맸다.

 

결국에 처음 왔던 감 대로

도수분포표 정렬 할 때의 방식을 응용해서 풀었다.

 

정수 범위가 -10,000,000 ~ +10,000,000 이므로 20,000,000 이라고 보면 되고

int는 4바이트니까 총 80,000,000 byte의 공간이 필요한데, 메모리 제한이 256MB이므로 충분하다고 판단했다.

 

입출력은 속도가 빠른 C의 입출력을 가져와 썼다.

#include <cstdio>
#include <iostream>
using namespace std;

int arr[20000000];

int main() {
    int N, M, temp;
    
    scanf("%d", &N);
    
    for(int i = 0; i < N; i++) {
        scanf("%d", &temp);
        
        arr[temp + 10000000]++;
    }
    
    scanf("%d", &M);
    for(int i = 0; i < M; i++) {
        scanf("%d", &temp);
        printf("%d ", arr[temp + 10000000]);
    }
    
}

 

풀이를 검색해보니, 많은 분들이 lower_bound , upper_bound를 이용해서 푸셨다.

lower_bound와 upper_bound는 이진 탐색인 binary_search 유형의 알고리즘이다. 그러므로 오름차순 정렬은 전제조건이다.

 

lower_bound : 찾으려는 키 값보다 크거나 같은 숫자가 처음 등장하는 위치를 찾는데 사용

upper_bound : 찾으려는 키 값을 초과한 숫자가 맨 처음 등장하는 위치를 찾는데 사용

참고 : chanhuiseok.github.io/posts/algo-55/    

 

처음에는 binary_search를 구현했던 것에 직접 lower_bound와 upper_bound를 구현하려 했고, 이렇게 구현했다.

#include <iostream>
#include <algorithm> // sort 함수 사용 위해
#include <cstdio>

using namespace std;

int ori[20000000];
int N;
int key[20000000];
int M;

int bin_search(int a[], int n, int key, bool is_lower) {

    int pl = 0; // 검색 범위 맨 앞의 인덱스
    int pr = n - 1; // 검색 범위 맨 끝의 인덱스
    int pc; // 검색 범위 한가운데의 인덱스

    do {
        pc = (pl + pr) / 2;

        if(a[pc] == key) {
            if(is_lower) {
                //최악의 경우 O(N)이 될 수 있는게 문제인듯.
            while(pc - 1 >= 0 && a[pc - 1] == key)
                pc--;
            } else {
                while(pc + 1 <= N - 1 && a[pc + 1] == key)
                    pc++;

            }
            return pc;
        }
        else if(a[pc] < key)
            pl = pc + 1;
        else if(a[pc] > key)
            pr = pc - 1;

    } while(pl <= pr);

    return -1; // 검색 실패

}


int main() {
    int i, upper, lower;

    scanf("%d", &N);

    for(i = 0; i < N; i++) {
        scanf("%d", &ori[i]);
    }

    scanf("%d", &M);

    for(i = 0; i < M; i++) {
        scanf("%d", &key[i]);
    }

    sort(ori, ori + N); // 배열, 배열 + 요소수

    for(int i = 0; i < M; i++) {

        lower = bin_search(ori, N, key[i], true);
        upper = bin_search(ori, N, key[i], false);

        if(lower == -1)
            printf("0 ");
        else if(lower == upper)
            printf("1 " );
        else
            printf("%d ", upper - lower + 1);
    }

}

이 코드는 시간초과 결과를 받았다.

이유를 알아봤더니, 내가 놓치고 있던 부분이 있었다. 바로, 최악의 경우였다.

참고 : www.acmicpc.net/board/view/64729

위 처럼 구현하지 말고, 값을 찾은 이후에도 계속해서 동일한 이분탐색 방식으로 진행했어야 했다.

직접 구현하신 분들의 예제는 아래에 있는데, 문제점이 있다. 값이 없을 경우에 대한 처리가 조금 애매하다는것..

skytitan.tistory.com/75  yhwan.tistory.com/10 

생각하다가 머리가 너무 아플 것 같아서, 그냥 C++의 <algorithm> 라이브러리에 있는 lower_bound와 upper_bound를 감사히 쓰기로 했다.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int N, M, temp;
    
    vector<int>::iterator lower;
    vector<int>::iterator upper;

    vector<int> v;
    
    scanf("%d", &N);
    
    for(int i = 0; i < N; i++) {
        scanf("%d", &temp);
        v.push_back(temp);
    }
    
    sort(v.begin(), v.end());
    
    scanf("%d", &M);
    
    for(int i = 0; i < M; i++) {
        scanf("%d", &temp);
        
        lower = lower_bound(v.begin(), v.end(), temp);
        upper = upper_bound(v.begin(), v.end(), temp);
        
        printf("%d ", upper - lower);
    }
    
}

lower과 upper변수가 담고 있는 결과는 vector iterator이므로 인덱스 값을 얻고 싶으면

 

lower - v.begin()

upper - v.begin()

해주면 된다.

 

참고로 없는 값을 찾을 경우에도 명분에 맞게 잘 작동한다.

ex)

{1, 2, 3, 4, 5} 에서 6을 찾는다

lower - v.begin() = 5

upper - v.begin() = 5

{1, 10, 20, 30, 40} 에서 25를 찾는다

lower - v.begin() = 3

upper - v.begin() = 3

 

 

역시 문제를 풀더라도, 다른 사람들의 풀이를 보는 것이 알아가는 것도 많고 학습에 도움이 많이 되는 것 같다.

 

 

∙ lower_bound, upper_bound 함수 참고

torbjorn.tistory.com/269

blockdmask.tistory.com/168