[백준/BOJ] - 1920번 python 풀이 - 이분 탐색(Binary Search)

---

Key Point

이 문제는 시간 초과와 메모리 초과로 인해 코드를 여러번 다시 작성했던 문제이다.

이분탐색에 대한 알고리즘을 알면 해결된다는 조언에 해당 알고리즘을 조사하여 해결하였다.

 

알게 된 문법

for value in enumerate(lists2):    
    if len_temp < int(value[1]):
        print(0)
        go = 0        
        
    if go == 1:
        if temp[int(value[1])-1] == 1:            
            print(1)
        else:
            print(0)               
    go = 1

다음과 같이 반복문을 사용하면 리스트에 있는 value의 값을 꺼내 쓸 수 있다. index의 값 또한 사용 가능.

하지만 해당 value는 tuple 타입이기 때문에 int(value[1])로 선언해야 value를 받을 수 있다. index의 값은 value[0]을 통해 얻을 수 있다. 

아니면 for문 선언할 때 for index, value in enumerate(lists2): 이런식으로 선언해서 사용 가능.

 

---

정답 코드

import sys
N = int(sys.stdin.readline())
lists1 = list(map(int,sys.stdin.readline().split()))

M = int(sys.stdin.readline())
lists2 = list(map(int,sys.stdin.readline().split()))

lists1.sort()

def algo(target, P_list): # sort가 된 list가 들어감
    length = len(P_list)    
    left = 0 
    right = length-1

    while left<=right:
        mid = (left+right)//2
        if P_list[mid] == target:
            return 1            
        elif P_list[mid]>target:
            right = mid-1
        else :
            left = mid+1
    return 0
    
for i in range(M):
    print(algo(lists2[i],lists1))

---

시간 초과 case1

import sys
N = int(sys.stdin.readline())
lists1 = list(map(int,sys.stdin.readline().split()))

M = int(sys.stdin.readline())
lists2 = list(map(int,sys.stdin.readline().split()))

cnt = 0

for i in range(N):
    if lists1.count(lists2[i]) != 0:
        print(1)
    else:
        print(0)

---

시간 초과 case2

import sys
N = int(sys.stdin.readline())
lists1 = list(map(int,sys.stdin.readline().split()))

M = int(sys.stdin.readline())
lists2 = list(map(int,sys.stdin.readline().split()))
num = 0
cnt = 0
for i in range(M): #찾을거
    while True:
        if lists2[i] == lists1[num]:
            cnt+=1
            lists1.remove(lists1[num])                        
            break #while 탈출
        num+=1
        if num == len(lists1):
            num = 0
            break

    if cnt == 1:
        print(1)
        cnt = 0
        num=0
    else:
        print(0)
        num=0

---

시간 초과 case3

import sys
N = int(sys.stdin.readline())
lists1 = list(map(int,sys.stdin.readline().split()))

M = int(sys.stdin.readline())
lists2 = list(map(int,sys.stdin.readline().split()))

cnt = 0

for i in range(N):
    if lists1.count(lists2[i]) != 0:
        lists1.remove(lists2[i])
        print(1)
    else:
        print(0)

---

메모리 초과

import sys
N = int(sys.stdin.readline())
lists1 = list(map(int,sys.stdin.readline().split()))

M = int(sys.stdin.readline())
lists2 = list(map(int,sys.stdin.readline().split()))
go = 1
cnt = 0
len_temp = len(lists1)
temp = [0 for i in range(max(lists1))]
for i in range(max(lists1)):
    temp[lists1[i]-1] = 1
for value in enumerate(lists2):    
    if len_temp < int(value[1]):
        print(0)
        go = 0        
        
    if go == 1:
        if temp[int(value[1])-1] == 1:            
            print(1)
        else:
            print(0)               
    go = 1