(백준 10815) 숫자 카드

 

문제

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

10815번: 숫자 카드

 

정답코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <set>

using namespace std;
#define Test 0

int num1 = 0;
int num2 = 0;
int arr1[500001] = {
    0,
};
int arr2[500001] = {
    0,
};

void binary(int k, int n)
{
    // n은 검색하고자 하는 값,찾는 값의 k는 배열의 길이
    int start_index = 0;
    int end_index = k - 1;
    while (start_index <= end_index)
    {
        int mid_index = (start_index + end_index) / 2;
        if (arr1[mid_index] == n)
        {
            cout << "1 ";
            return;
        }
        else
        {
            if (arr1[mid_index] > n)
            {
                end_index = mid_index - 1;
            }
            else
            {
                start_index = mid_index + 1;
            }
        }
    }
    cout << "0 ";
}

int main()
{
    cin >> num1;
    for (int a = 0; a < num1; a++)
    {
        cin >> arr1[a];
    }
    cin >> num2;
    for (int a = 0; a < num2; a++)
    {
        cin >> arr2[a];
    }
    sort(arr1, arr1 + num1);
    for (int i = 0; i < num2; i++)
    {
        binary(num1, arr2[i]);
    }
}

 

정답해설

탐색의 방법에서 입력의 개수와, 시간을 확인하고 시간복잡도를 확인해서

만약 시간이 부족하다고 생각되면 바로 이진탐색이 생각이 나야한다.

 

void binary(int k, int n)
{
    // n은 검색하고자 하는 값,찾는 값의 k는 배열의 길이
    int start_index = 0;
    int end_index = k - 1;
    while (start_index <= end_index)
    {
        int mid_index = (start_index + end_index) / 2;
        if (arr1[mid_index] == n)
        {
            cout << "1 ";
            return;
        }
        else
        {
            if (arr1[mid_index] > n)
            {
                end_index = mid_index - 1;
            }
            else
            {
                start_index = mid_index + 1;
            }
        }
    }
    cout << "0 ";
}

이게 이진탐색의 기본적인 코드 유형, 이러한 방법으로 탐색하는것이 훨신 빠르다.

굳이 백터를 사용안하고 다양한 방법이나, 오히려 간단한 방법을 생각하는것도 나쁘지 않다. 

한가지 방법에 고정될 필요가 없는듯.

 

유형2. 이진탐색의 경우, set을 사용할수 있다.

기본적으로 set의 경우에는 중복을 허용하지 않으며, 이진트리로 구현되어있기 때문에 검색을 하면 자연스럽게 이진탐색을 하게 된다.

따라서 set을 사용하는 방법도 가능하다.

#include <bits/stdc++.h>
#include <unordered_set>

using namespace std;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n, m;
	cin >> n;

	unordered_set<int> s;
	for (int i = 0; i < n; i++)
	{
		int num;
		cin >> num;
		s.insert(num);
	}

	cin >> m;
	vector<int> res;
	for (int i = 0; i < m; i++)
	{
		int num;
		cin >> num;
		res.push_back(s.find(num) != s.end() ? 1 : 0);
	}

	for (auto& i : res)
		cout << i << ' ';
	return 0;
}

처음 내가 생각한 방법도 이거였지만, 아무튼 구현하는게 의미있었다.

 

ㅠㅠ 나존나못하는듯..  하다보면 늘겠지 .. 1일1코딩가보자고..