[백준] 1920번: 수 찾기

[백준] 1920번: 수 찾기

[링크]

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

 

 

[문제]

 

 

[풀이]

핵심

• 전형적인 이분 탐색 문제이다.
• 이 문제는 이분 탐색 말고도 다른 방법도 있다.
• 자세한 이분 탐색 알고리즘은 (여기서 추후 추가) 확인하기 바란다.

 

<이분 탐색>

1. 이분 탐색을 위해서 처음 integer_list를 정렬한다.
2. find_value를 순회하면서 각 값을 이분 탐색한다.
3. start=0, end=(list길이)-1 으로 두고 mid=(start+end)/2
4. mid의 값보다 val가 작으면 end=mid-1, 크면 start=mid+1, 같으면 1을 반환하고 함수를 종료.
5. while문이 끝날 때까지 함수가 종료 되지 않았다면 존재하지 않으므로 0을 반환한다.

 

<Set 자료형 이용>

1. set자료형에서 값을 찾는 건 O(1)의 시간복잡도를 가진다는 걸 이용한다.
2. 먼저 integer_list를 set자료형으로 바꿔준다.
3. find_value를 순회하면서 in 예약어를 사용하여 integer_list에 있는지 파악한다.

 

 

[이분 탐색 코드]

# 1920번(수 찾기)
# 이분 탐색
def binary_search(integer_list,val):
    start=0
    end=len(integer_list)-1
 
    while start<=end:
        # 중간값은 start와 end의 가운데 값
        mid=(start+end)//2
        if val<integer_list[mid]:
            end=mid-1
        elif val>integer_list[mid]:
            start=mid+1
        else:
            return '1'
    return '0'
 
 
N=input()
integer_list=list(map(int,input().split()))
M=input()
find_value=list(map(int,input().split()))
 
# 먼저 주어진 정수 값을 정렬해 준다.
integer_list.sort()
result=''
for val in find_value:
    result+=binary_search(integer_list,val)+'\n'
print(result)

 

 

[Set 자료형 이용 코드]

# 1920번(수 찾기)
# set을 이용한 풀이
N=input()
integer_list=set(input().split())
M=input()
find_value=input().split()
 
# 먼저 주어진 정수 값을 정렬해 준다.
result=''
for val in find_value:
    if val in integer_list:
        result+='1\n'
    else:
        result += '0\n'
 
print(result)