[1920번] 수 찾기 / python3 (첫 등장! 이분(이진)탐색)

문제 링크: https://www.acmicpc.net/problem/1920

1920번: 수 찾기

---

❌ 1~2차시도 실패

시간초과 실패였다......

혹시나 input( ) 때문인가 싶어서 sys이용해서 했지만 그래도 시간초과...

n=int(input())
n_list=list(map(int,input().split()))
m=int(input())
m_list=list(map(int,input().split()))
 
for i in m_list:
    if i in n_list:
        print(1)
    else:
        print(0)

 

문제 밑에 알고리즘 분류를 보니 '이분탐색'이라고 써있다.

이분 탐색... 이 분 탐색.....

이 분을 탐색하시오......

앗, 죄송 ㅋㅋㅋㅋㅋㅋㅋ

샛길 공부가 시작되었다.

◾샛길공부링크는여기 👉

개념 : https://coding-nurse.tistory.com/41?category=975208

문제풀기 : https://coding-nurse.tistory.com/42?category=975208

---

❓ 정답은 ??

[재귀함수 사용]

n=int(input())
n_list=list(map(int,input().split()))
n_list.sort( )
 
m=int(input())
m_list=list(map(int,input().split()))
 
def binary(array, target, start, end):
    if start > end:
        return 0 #없을 떄
    mid = (start+end)//2
    #조건1) 중간점이 타켓
    if target == array[mid]:
        return 1 #있을 떄
    #조건2) 중간점보다 작음(끝점을 중간점 이전으로 변경)
    elif target < array[mid]:
        return binary(array, target, start, mid-1)
    #조건3) 중간점보다 큼(시작점을 중간점 다음으로 변경)
    else:
        return binary(array, target, mid+1, end)
 
for target in m_list:   #타겟을 반복문으로 돌리고
    start = 0
    end = len(n_list)-1
    print(binary(n_list, target, start, end))

[반복문 사용]

n=int(input())
n_list=list(map(int,input().split()))
n_list.sort( )
 
m=int(input())
m_list=list(map(int,input().split()))
 
def binary(array,target,start,end):
    while start<=end:
        mid= (start+end)// 2
        
        #조건1) 중간점이 타켓
        if array[mid]==target:
            return 1    #있을 때
        
        #조건2) 중간점보다 작음(끝점을 중간점 이전으로 변경)
        elif array[mid]>target:
            end= mid-1
        
        #조건3) 중간점보다 큼(시작점을 중간점 다음으로 변경)
        else:
            start= mid+1
    return 0    #없을 때
 
for target in m_list:   #타겟을 반복문으로 돌리고
    start = 0
    end = len(n_list)-1
    print(binary(n_list, target, start, end))

---

💯 풀이 과정

이진(이분) 탐색 공식을 사용해서 문제를 풀이하였다.

	없음 0	있음 1
재귀함수 이용	시작점 > 끝점 (없어서, 시작점을 mid+1을 계속 수행하다보니)	타겟이 중간점과 같아질 때
반복문 이용	while 반복문 속 조건에 해당하는 것이 없을 때	타겟이 중간점과 같아질 때

마지막 타겟 리스트를 for 반복문으로 돌려서 쓰는데 순간 헷갈려서 시간 잡아먹음.....ㅋ

---

😎오늘의 한줄평: 아는 문제 나왔다고 성급하게 하지말고 차근차근 풀어보자.