<문제 소개>
<소스 코드> - map
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <cmath>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstdlib>
using namespace std;
int main()
{
int N;
cin >> N;
map<int, bool> map;
for (int i = 0; i < N; i++)
{
int x;
cin >> x;
map.insert({ x, true });
}
int M;
cin >> M;
vector<int> v;
for (int i = 0; i < M; i++)
{
int x;
cin >> x;
v.push_back(x);
}
for (int i = 0; i < v.size(); i++)
{
if (map[v[i]]) cout << "1";
else cout << "0";
if (i != v.size() - 1) cout << " ";
}
return 0;
}<소스코드> - 이분탐색
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <cmath>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstdlib>
using namespace std;
int first[500000];
int second[500000];
void BinarySearch(int size, int curVal)
{
int lowIndex = 0;
int highIndex = size - 1;
while (lowIndex <= highIndex)
{
int midIndex = (lowIndex + highIndex) / 2;
if (curVal == first[midIndex])
{
// 값을 찾은 경우
cout << "1";
return;
}
else
{
if (curVal > first[midIndex])
{
// 찾는 값이 중간 값보다 작은 경우
lowIndex = midIndex + 1;
}
else
{
// 찾는 값이 중간 값보다 큰 경우
highIndex = midIndex - 1;
}
}
}
// 값이 찾지 못한 경우
cout << "0";
}
int main()
{
int N;
cin >> N;
for (int i = 0; i < N; i++)
{
cin >> first[i];
}
// 첫번째 카드를 정렬해줌
sort(first, first + N);
int M;
cin >> M;
for (int i = 0; i < M; i++)
{
cin >> second[i];
}
// 첫번째 카드더미에서 이분탐색을 이용해 두번째 카드가 있는지 확인한다.
for (int i = 0; i < M; i++)
{
BinarySearch(N, second[i]);
cout << " ";
}
return 0;
}<풀이과정> - map
1. int형 key 값을 가지고, bool형 value 값을 가지는 map을 선언
2. N을 입력받고 N만큼 반복하며 다음 입력을 받으면서 map에 해당 입력값과 true를 원소로 넣어준다.
3. M을 입력받고 벡터 v를 선언하여 M만큼 반복하며 검사할 값들을 입력받으며 v에 원소로 넣어준다.
4. 벡터 v를 돌면서 map에서 해당 값인 v[i]를 key값으로 하여 true인 원소들을 찾은경우 "1"을 출력해주고, 아닌 경우에는 "0"을 출력해준다.
5. 마지막을 제외한 각 원소들 사이에는 띄어쓰기가 있어야 되므로 마지막을 제외하고 매 반복마다 공백을 출력해준다.
<풀이과정> - binary search
1. 첫번째 카드와 두번째 카드를 담을 배열을 외부에서 전역변수로 각각 선언 후 최대 크기 500,000만큼 초기화 시켜줌
2. 첫번째 카드 갯수 N개를 입력받고, N만큼 반복하며 입력된 값들을 배열 first에 넣어줌
3. sort를 이용해 첫번째 카드더미 first를 오름차순으로 정렬함
4. 두번째 카드 갯수 M개를 입력받고, M만큼 반복하며 입력된 값들을 배열 second에 넣어줌
5. 해당 원소들을 접근하며 BinarySearch() 함수를 이용해 첫번째 카드에 해당 값이 있는지 확인함
6. BinarySearch()
6-1. 인자로 첫번째 카드더미의 크기 size와, 두번째 카드더미에서 검색할 값 curVal를 받아옴
6-2. 현재 가장 작은 인덱스 값 lowIndex는 0으로 가장 큰 인덱스 값 highIndex은 size -1로 선언함
6-3. lowIndex가 highIndex보다 크지 않을 동안 반복하면서 검색을 진행
6-4. 현재 첫번째 카드더미의 중간값이 위치한 인덱스를 나타내는 midIndex를 lowIndex와 highIndex를 이용해 구함[(lowIndex+highIndex)/2]
6-5. 첫번째 카드더미의 중간값 first[midIndex]와 검색할 값 curVal를 비교
6-6. curVal와 중간값이 같을 경우 1을 출력해주고 리턴함
6-7. curVal가 더 클 경우 curVal는 midIndex+1과 highIndex 사이에 있는 것이므로 lowIndex를 midIndex+1로 바꿔주고 다시 다음 반복을 진행
6-8. curVal가 더 작을 경우 curVal는 lowIndex와 midIndex-1 사이에 있는 것이므로 highIndex를 midIndex-1로 바꿔주고 다시 다음 반복을 진행
6-9. lowIndex가 highIndex보다 커져서 반복문을 빠져나온다면 curVal값은 첫번째 카드더미안에 없는 것이므로 0을 출력한다.
7. second 배열의 각 원소마다 접근하여 Binary(N, second[i])를 한 뒤, 공백을 출력해준다.
<코멘트>
처음에 이중 for문을 이용해서 풀었는데 역시나 시간초과가 나와서 map을 이용해서 풀어보았다.
집합과 맵 파트라서 map을 이용하여 푸는건줄 알았는데 검색해보니 다들 이분탐색으로 푸셨다.
그래서 나도 이분탐색으로 풀어도 보았다!
이분탐색으로 풀었을 때 자료구조를 벡터로 하면 시간초과가 발생하였고, 배열로 바꾸니깐 해결되었다!
cf) 배열 vs 벡터
- 벡터를 사용해야하는 경우
1. 데이터의 개수가 가변적인 경우
2. 검색이 빈번하게 일어나지 않는 경우
- 검색을 자주한다면 map, set, hash_map을 사용하는 것이 좋음
3. 중간에 데이터 삽입/삭제가 일어나지 않는 경우
- 배열 기반 컨테이너 이므로 비효율적임
4. 데이터에 랜덤접근(어디에나 똑같은 시간으로 접근)이 필요할 경우
- 벡터 사용시 주의할 점
1. 동적인 메모리 할당을 지원하지만 상당한 비용이 필요함
2. 한 번에 메모리를 할당하는 함수인 reserve() 함수 사용을 습관화 하는 것이 필요함
<제출결과>
- 첫번째는 이분탐색으로 푼 결과이고, 두번째는 맵으로 풀었을 때의 결과이다.
