Easy is Perfect

[백준] 10815번 C/C++ 풀이 _ 숫자 카드

  • melonicedlatte
  • Feb 24, 2018


출처 : https://www.acmicpc.net/problem/10815

숫자 카드 성공 풀이

시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초256 MB85353751269145.227%

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 숫자 M개가 주어졌을 때, 이 숫자가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N (1 ≤ N ≤ 500,000)이가 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 숫자가 주어진다. 숫자 카드에 적혀있는 숫자는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 숫자가 적혀있는 경우는 없다.

셋째 줄에는 M (1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 숫자가 주어지며, 이 숫자는 공백으로 구분되어져 있다. 이숫자도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

출력

첫째 줄에 입력으로 주어진 M개의 숫자에 대해서, 각 숫자가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

예제 입력 

5
6 3 2 10 -10
8
10 9 -5 2 3 4 5 -10

예제 출력 

1 0 0 1 1 0 0 1

힌트

출처

알고리즘 분류

>> 풀이 

이 문제는 이진 탐색으로 분류가 되어 있지만, 배열을 사용해도 메모리 초과가 되지 않고 상수 시간 내에 접근이 가능했다.
다만 시간이 좀 걸린 것은 cin, cout 을 사용해서 속도가 느려져 문제를 '시간초과' 로 틀린 점이다.
scanf 와 printf 를 애용해야겠다. 

>> 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
 
using namespace std;
 
// 상근이 가지고 있는 숫자를 1로 표기
// -10000000 이 시작점이다 
int sang_gen_have[10000000 * 2 + 1] = { 0 };
int N, M;
 
int main() {
    scanf("%d", &N);
    int sub;
    // 배열에 존재하는 숫자는 1로 표기 
    for (int i = 0; i < N; i++) {
        scanf("%d", &sub);
        sang_gen_have[sub + 10000000] = 1;
    }
 
    // 배열에 존재하는 숫자면 1 출력 , 아니면 0 출력 
    scanf("%d", &M);
    for (int i = 0; i < M; i++) {
        scanf("%d", &sub);
        if (sang_gen_have[sub + 10000000]) printf("%d ", 1);
        else printf("%d ", 0);
    }
 
    return 0;
}
cs



Search