[Python] 백준 '수 찾기' 1920번| 해쉬, 배열, 구현 자료구조

다른 문제 모음집

문제

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

 

입력

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

 

출력

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

---

반응형

풀이

풀이 1 (149796KB, 228ms)

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

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

• set 자료형을 사용함

풀이 2 (50732KB, 212ms)

N = int(input())
array = {i: 1 for i in map(int, input().split())}  # 모든 key값에 value를 1로 줌.
M = int(input())
x = list(map(int, input().split()))

for data in x:
    print(array.get(data, 0))  # get 함수를 이용해서 key값의 value인 1을 반환하고, key값이 존재하지 않으면 0을 반환함

• dict 자료형 + get 함수 조합
• .get(x, y) 함수는 Key 값에 대응하는  Value를 반환하고, 수가 존재하지 않으면 y를 반환함. X라는 정수가 array에 있으면 value인 1을 반환하고, 없으면 0을 반환함

set 자료형에서 if 문을 사용했기 때문에 메모리 용량이 크고 시간이 좀 더 걸렸음. dict + get 함수의 조합이, 차지하는 메모리 용량도 적고 빠름.

출처

• 데이터를 추가한 사람: BaaaaaaaaaaarkingDog, djm03178