[해시/배열] BAEKJOON 1920번 '수 찾기'문제 (C++/python)

문제 : www.acmicpc.net/problem/1920

1920번: 수 찾기

 

 

• python

    python을 이용했을 때, set자료형을 이용할 수 있다.

 

    set자료형은 집합처럼 중복없이 저장할 수 있고, 요소의 존재 여부를 간단하게 판단할 수 있다.

n = int(input())

array = set(map(int,input().split()))
m = int(input())
x = list(map(int,input().split()))

for i in x:
    if i not in array:
        print('0')
    else:
        print('1')

 

 

 

※ set 자료형

 

집합 자료형을 뜻하며, 앞서 언급한 것 처럼 중복없이 저장을 한다. 또한 값들을 순서 없이 저장한다.

>>> s1 = set([1,2,3])
>>> s1
{1, 2, 3}

>>> s2 = set("Hello")
>>> s2
{'e', 'H', 'l', 'o'}

 

 

set자료형을 통해 교집합, 합집합, 차집합을 구할 수 있다.

 

1. 교집합

>>> s1 = set([1,2,3])
>>> s2 = set([2,3,4])
>>> s1 & s2
{2,3}
>>> s1.intersection(s2)
{2,3}

2. 합집합

>>> s1 = set([1,2,3])
>>> s2 = set([4,5,6])
>>> s1 | s2
{1,2,3,4,5,6}
>>> s1.union(s2)
{1,2,3,4,5,6}

3. 차집합

>>> s1 = set([1,2,3,4])
>>> s2 = set([3,4,5,6])
>>> s1 - s2
{1,2}
>>> s2 - s1
{5,6}

 

 

set에 자료를 추가하거나 삭제할 수도 있다.

 

1. 추가

>>> s1 = set([1,2,3])
>>> s1.add(4)
>>> s1
{1,2,3,4}
>>> s1.update([5,6,7])
>>> s1
{1,2,3,4,5,6,7}

 

2. 삭제

>>> s1 = set([1,2,3])
>>> s1.remove(2)
>>> s1
{1,3}

 

 

 

 

• c++

    배열A에 첫번째 집합의 값을 입력받아 sort를 이용하여 오름차순으로 정렬한다.

 

    이후 입력되는 값을 2진탐색을 이용하여 배열A에 존재하는지 찾는다.

 

    탐색 대상이 절반씩 줄어드는 2진탐색의 시간복잡도는 O(logn)이므로 총 10⁵개의 데이터를 비교하기 위해 2초는 충분하다.

    (rough하게 계산해도 M번 for문을 돌며 find()로 들어가기 때문에 최대 10⁵ * log(10⁵)가 걸린다.)

 

#include <iostream>
#include <algorithm>

using namespace std;

void find(int num, int N, int arr[]){
    
    int start = 0, fin = N, result=0;
    int middle;
 
    while(fin - start >= 0){
        middle = (start + fin)/2;
        if(arr[middle] == num){
            result = 1;
            break;
        }
        else if(num < arr[middle])
            fin = middle-1;
        else if(arr[middle] < num)
            start = middle+1;
            
    }
    printf("%d\n",result);
}

int main(){
    
    int N, M;
    scanf("%d",&N);
    int A[N];
    for(int i=0 ; i< N ; i++){
        scanf("%d",&A[i]);
    }
    sort(A , A+N);
    scanf("%d",&M);
    for(int i=0 ; i< M ; i++){
        int tmp;
        scanf("%d",&tmp);
        find(tmp, N, A);
        
    }
    
    return 0;
}

 

    초기 cin, cout을 사용했을 때 시간초과가 발생했다.

 

    endl을 사용할 때 뿐만 아니라 cin, cout을 사용할 때에도 많은 시간이 걸렸다.

 

    cin대신 scanf, cout 대신 printf를 사용해서 이를 해결할 수 있었다.