10815번: 숫자 카드
숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.
https://www.acmicpc.net/problem/10815
문제
숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 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을 공백으로 구분해 출력한다.
예제 입력 1
5
6 3 2 10 -10
8
10 9 -5 2 3 4 5 -10예제 출력 1
1 0 0 1 1 0 0 1
풀이
#include <iostream>
#include <map>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N = 0;
map<int, int> sanggeun;
cin >> N;
for(int i = 0; i < N; i++)
{
int temp = 0;
cin >> temp;
sanggeun[temp] = 1;
}
cin >> N;
for(int i = 0; i < N; i++)
{
int temp = 0;
cin >> temp;
if(sanggeun[temp]) cout << 1 << ' ';
else cout << 0 << ' ';
}
}| 메모리 (KB) | 시간 (ms) | 코드 길이 (B) |
| 36608 | 576 | 495 |
문제 분류에 따라 맵으로 풀어보았다. 시간이나 메모리가 너무 많이 나와 신경 쓰인다.
1️⃣
먼저 상근이가 가지고 있는 카드를 입력해준다. 문제에서 카드 중 겹치는 수가 없다고 했으니 키가 중복될 일이 없다.
2️⃣
이후 비교할 카드들의 개수와 숫자인 키를 검사한다.
3️⃣
0이면 false, 그 외 숫자라면 true기 때문에 비교할 카드들과 상근이가 가지고 있는 카드들의 숫자를 비교할 수 있다.
➕ 재풀이
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int BinarySearch(vector<int> &sanggeun, int target, int left, int right)
{
int middle = (left + right) / 2;
if(left > right) return -1;
else if(sanggeun[middle] == target) return middle;
else if(sanggeun[middle] < target)
return BinarySearch(sanggeun, target, middle+1, right);
else return BinarySearch(sanggeun, target, left, middle - 1);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N = 0;
int M = 0;
vector<int> sanggeun;
vector<int> compare;
cin >> N;
for(int i = 0; i < N; i++)
{
int temp = 0;
cin >> temp;
sanggeun.push_back(temp);
}
cin >> M;
for(int i = 0; i < M; i++)
{
int temp = 0;
cin >> temp;
compare.push_back(temp);
}
sort(sanggeun.begin(), sanggeun.end());
for(int i = 0; i < M; i++)
{
if(BinarySearch(sanggeun, compare[i], 0, N - 1) != -1) cout << 1 << ' ';
else cout << 0 << ' ';
}
}| 메모리 (KB) | 시간 (ms) | 코드 길이 (B) |
| 8296 | 236 | 964 |
알고리즘 분류를 보니 이분 탐색이라고 적혀있었다. 그래서 이분 탐색 방법을 다시 학습하고 풀어보았다.
1️⃣
상근이의 카드들의 숫자와 비교할 카드들의 숫자를 입력 받는다.
2️⃣
원활한 비교를 위해 상근이가 가지고 있는 카드들을 오름차순으로 정렬해준다.
3️⃣
이분 탐색에 의해 있다면 middle 값을, 없다면 -1을 반환하기 때문에 비교할 카드에 상근이가 가진 카드가 있는지 여부를 알 수 있다.
Uploaded by N2T