[백준] 1920번 : 수 찾기

유형 : 해시, 배열, 구현

[예제 입력]

5
4 1 5 2 3
5
1 3 7 9 5

[예제 출력]

1
1
0
0
1

---

핵심 아이디어
1. 특정 정수의 등장 여부만을 간단히 체크
2. dictionary 자료형을 해시처럼 사용 가능(python)
3. set 자료형을 이용하면 간단히 풀 수 있음

 

1. 내 풀이

- 시간 초과..

- 찾아보니 많은 사람들이 나처럼 틀리는 것 같다. (순차탐색 문제)

N = int(input())
list1 = list(map(int,input().split(' ')))
M = int(input())
list2 = list(map(int,input().split(' ')))

for i in range(M):
    num = list2[i]
    check = 0
    for j in range(len(list1)):
        if num == list1[j]:
            check = 1

    if check == 0:
        print(0)
    else:
        print(1)

다시 고쳤는데 시간 초과가 나왔다

N = int(input())
list1 = list(map(int,input().split(' ')))
M = int(input())
list2 = list(map(int,input().split(' ')))

for i in range(M):
    num = list2[i]
    if num in list1:
        print(1)
    else:
        print(0)

또 다시 고쳤는데 시간 초과가 나왔다... 순차 탐색에서 문제가 있는 것 같다.

N = int(input())
list1 = list(map(int,input().split()))
M = int(input())
list2 = list(map(int,input().split()))

for i in list2:
    if i in list1:
        print(1)
    else:
        print(0)

 

2. 정답 풀이(자료형 이용)

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')

출처 : 패스트캠퍼스 - 알고리즘 / 기술면접 완전 정복 올인원 패키지 Online

 

3. 다른 풀이(이분 탐색/이진 탐색)

- 검색해봤더니 이분 탐색으로 푸는 방법이 또 존재하였다.

def binary_search(a,x,start,end):
	if start > end:
        return 0
    
    m = (start+end) // 2
    
    if a[m] == x:
    	return 1
    elif a[m] > x:
    	return binary_search(a,x,start,m-1)
    else:
    	return binary_search(a,x,m+1,end)
 
 n = int(input())
 a = list(map(int, input().split())
 m = int(input())
 m_l = list(map(int, input().split()))
 a = sorted(a)
 
 for m in m_l:
    if binary_search(a,m,0,n-1):
        print(1)
    else:
    	print(0)

위의 코드는 https://alpyrithm.tistory.com/2 의 풀이 2 방법을 가져온 것이다. 이 외에 다른 풀이도 써있기 때문에 한 번 보는 것을 추천한다.

 

- 같은 풀이지만 살짝 다른 코드 (출처 : 알고리즘 / 기술면접 완전 정복 올인원 패키지 Online)

# N = 5
# N_list = [4,1,5,2,3]
# M = 5
# M_list = [1,3,7,9,5]

N_list.sort()

def binary_search(value, start, end):
    # print(value, start, end)
    if start > end:
    	return False
        
    m = (start+end) // 2
    if N_list[m] > value:
    	return binary_search(value, start, m-1)
    elif N_list[m] < value:
    	return binary_search(value, m+1, end)
    else:
    	return True
        
 for item in M_list:
 	if binary_search(item, 0, N-1):
    	print(1)
    else:
    	print(0)

 

참고 : 

풀이1 : https://yoonsang-it.tistory.com/14

백준 1920번 파이썬 풀이: 수 찾기

자세한 풀이2 : https://chancoding.tistory.com/44

[Python] 백준 1920번 수 찾기 - 두가지 풀이:이분탐색과 자료형