[백준 10816/C언어] 숫자 카드 2 풀이

백준 10816번 문제를 풀어보았습니다.

백준 10816번: https://www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

 

 

문제 내용은 다음과 같습니다. 

 

 

 

 이 문제는 검색이 용이하도록 입력받은 숫자 카드를 저장하는 것이 관건입니다. 하지만 low level languae에 해당하는 c언어의 특성상 검색이 용이한 배열을 만들어 저장하기란 쉽지 않습니다. 그래서 저는 주로 주어지는 숫자를 인덱스, 즉 key값으로 하는 hash table을 만들어서 필요한 정보(해당 값이 존재하는지 여부, 해당 값이 몇 번 중복되어 저장되어 있는지 여부 등)를 value값으로 저장하곤 합니다. 이 문제에서도 동일한 방법을 사용했습니다. 

 우리가 입력받은 숫자에 대해서 필요한 정보는 해당 숫자를 몇 번 입력받았는가 입니다. 따라서 int 배열을 선언해 주어서 해당되는 index를 계속해서 증가시켜 주면서 세어주면 됩니다. 이렇게 하면 추후 검색을 할 때에 인덱스에 검색하고자 하는 숫자만 넣어주면 손쉽게 우리가 원하는 정보를 얻을 수 있습니다.

 

 

 구조 자체가 어렵지 않으므로 바로 코드를 보겠습니다. 우선 전역변수로 NegativeCard와 PostivieCard 두 개의 배열을 선언해주었습니다. 이유는 index값으로 음수를 사용할 수 없는데, 문제에 따르면 숫자 카드에는 음수값이 적혀있을 수 있기 때문입니다. 이 외에도 음수값을 양수로 바꾸어서 다시 최댓값을 더해준 값을 인덱스로 사용하는 등 다양한 방법이 있지만 저는 그냥 배열 두 개를 선언해 주는 방법을 선택했습니다. 또한, 전역변수로 선언해 준 이유는 이렇게 하면 하나하나 0으로 초기화해주지 않아도 되기 때문에 사용이 용이합니다.

 그리고 N을 입력 받아서 가지고 있는 숫자카드를 입력받습니다. 이미 배열 전체 값이 0으로 초기화된 상태이므로 해당되는 인덱스에 1을 증가시켜주기만 하면 해당되는 숫자카드 개수가 카운트됩니다. 

 마지막으로 정보를 얻고자 하는 M개의 숫자 카드를 입력받아, 그 카드의 숫자의 인덱스에 저장된 값을 출력하기만 하면 원하는 정보를 출력할 수 있습니다.

#include <stdio.h>

int NegativeCard[10000001];
int PositiveCard[10000001];

int main() {
    int N, M;
    scanf("%d", &N);
    
    int card;
    for (int i = 0; i < N; i++) {
        scanf("%d", &card);
        if (card < 0) (NegativeCard[-card])++;
        else (PositiveCard[card])++;
    }
    
    scanf("%d", &M);
    for (int i = 0; i < M; i++) {
        scanf("%d", &card);
        if (card < 0) printf("%d ", NegativeCard[-card]); 
        else printf("%d ", PositiveCard[card]);
    }
}