[백준 1920] 수찾기(python 풀이)

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

1920번: 수 찾기

 

1. 문제 

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

2. 입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

 

3. 출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

 

---

4. 포인트

1.  시간 초과가 발생했을때 시간복잡도를 계산해보고 좀더 빠른 알고리즘을 적용해보자
2.  딕셔너리는 hash 자료구조를 통해 저장됨
3.  단순히 존재의 여부를 확인하는 방법으로는 set 자료형이 유용하다 (set 또한 내부적으로 hash로 저장됨)

 

4. 문제 풀이

  : 처음 시도에는 list 에서  in 연산자를 통해 시도했지만 역시나 시간 초과 되었다. list의 in은 시간 복잡도 O(n)을 가지므로 그보다 시간복잡도가 낮은 dictionary search를 사용해서 풀었다.( 정확히는 hash로 만들어진 dicionary)

시도 중 딕셔너리에 대한 잘못된 이해로 직접 hsah_function을 만들어 (key = value %8) 저장했지만 이 또한 시간 초과가 나서 서칭을 통해 dictionary 는 자체적으로 hash 형식으로 저장됨을 알게되어 다음과 같은 코드로 통과했다.

 서칭 도중 해당 문제는 set을 통해서도 많이 풀이됨을 알 수 있었다.  set 또한 내부적으로 hash를 통해 저장되면 값에 대한 유무를 확인할때 매우 유용하게 쓰일 수 있다. 

# 수찾기

# dictionay 를 통한 풀이 

from typing import DefaultDict

M = int(input())
dic = DefaultDict(list)

lst1 = list(map(int , input().split()))

for i in lst1:
    dic[i].append(1)

N = int(input())
lst2 = list(map(int , input().split()))


for i in lst2:
    if  i in dic[i] :
        print("1")
    else:
        print("0")

 

# 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")