[백준/C++] 10816번 숫자 카드 2

문제: www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

 

문제풀이

 

숫자카드에 적혀있는 숫자의 범위가 -10,000,000 ~ 10,000,000 으로 0 포함 20,000,001 의 크기의 int형 배열을 선언했을 때 80,000,008 바이트 약 80 MB의 메모리를 사용하게 되는데 문제의 메모리 제한은 256 MB로 넉넉하기 때문에 배열의 인덱스를 이용하여 문제를 풀었다.

 

배열 arr[20000001] 을 0으로 초기화시키고 상근이가 가지고 있는 숫자카드라면(해당 숫자의 입력이 들어온다면) 1을 더해주어 숫자카드의 개수를 저장한다.

 

배열의 인덱스는 음수일 수 없기 때문에 -1 ~ -10,000,000 의 수는 10,000,001 ~ 20,000,000 로 나타내었다.

 

 

코드

#include <iostream>

using namespace std;

int main(){
    ios::sync_with_stdio(false); cin.tie(NULL);

    int N;
    cin>>N;

    int numN;
    int arr[20000001] = {0,};
    for(int i=0; i<N; i++){
        cin>>numN;
        numN >= 0 ? arr[numN]++:arr[10000000-numN]++; //음수라면 10000001~20000000에 저장한다
    }

    int M;
    cin>>M;

    while(M--){
        int numM;
        cin>>numM;
        
        if(numM >= 0){ //인덱스를 이용한 숫자 갯수 출력
            cout<<arr[numM]<<" ";
        }
        else{
            cout<<arr[10000000-numM]<<" ";
        }
    }

    return 0;
}

 

 

결과

 

다른 풀이를 보니 이진 탐색(upper_bound, lower_bound)을 이용한 풀이도 있었습니다.

이진 탐색을 사용하면 -10,000,000 ~ 10,000,000 의 숫자를 모두 인덱싱할 필요 없어

낭비되는 메모리가 없어 낮은 공간 복잡도로 풀이가 가능합니다.