[Python] 백준 알고리즘 1920번 : 수 찾기

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

1920번: 수 찾기

 

 

👩‍💻문제 이해

list를 이용해 각각의 원소들을 비교하면 쉽게 풀릴 문제지만, 시간초과가 난다.

따라서 처음 주어지는 배열을 오름차순으로 정렬해 이분 탐색 알고리즘을 이용해 풀었다.

 

 

 

 

👩‍💻List만 사용  : 시간초과💀

import sys
n = int(input())
nli = sys.stdin.readline().split()
m = int(input())
mli = sys.stdin.readline().split()

for i in mli:
  if i in nli:
    print(1)
  else:
    print(0)

 

 

 

👩‍💻이분탐색 알고리즘 사용  : 성공🌈

n = int(input())
N = sorted(map(int, input().split()))
m = int(input())
M = map(int, input().split())

def binary(i, N, start, end):
    if start > end:
        return 0
    mid = (start+end)//2
    if i == N[mid]:
        return 1
    elif i < N[mid]:
        return binary(i, N, start, mid-1)
    else:
        return binary(i, N, mid+1, end)

for i in M:
    start = 0
    end = len(N)-1
    print(binary(i,N,start,end))

 

n = int(input())
N = sorted(map(int, input().split()))
# n개의 정수들을 받아 오름차순으로 정렬

m = int(input())
M = map(int, input().split())

 

# 이분탐색 알고리즘 함수 정의
# i : M 리스트에 들어있는 값, N : 오름차순으로 정렬된 list, start : 시작 index, end : 마지막 index

def binary(i, N, start, end):
    if start > end:
        return 0
       	# 모든 인덱스 검사 후 i가 N에 없을 경우 0 return
        
    mid = (start+end)//2
    # 중간값
    
    if i == N[mid]:
        return 1
        
    elif i < N[mid]:
        return binary(i, N, start, mid-1)
    # 값 i가 N의 중간값보다 작을 경우 마지막 위치를 중간으로 바꾼 뒤 다시 이분탐색 알고리즘 실행
    
    else:
        return binary(i, N, mid+1, end)
    # 값 i가 N의 중간값보다 클 경우 시작 위치를 중간으로 바꾼 뒤 다시 이분탐색 알고리즘 실행

 

for i in M:
    start = 0
    end = len(N)-1
    print(binary(i,N,start,end))
    
# M 리스트에 들어있는 원소 각각을 이분탐색 알고리즘을 통해 값 return

 

 

 

✨Point✨

이분탐색 알고리즘 정리