[백준] 1920번 수 찾기, python

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

1920번: 수 찾기

여러번의 시간 초과와 오류 끝에 드디어!! 제대로 코드를 구현했다.

첫번째 시간 초과 일 때는

아래 코드와 같이

완전 탐색으로 n^2 구현 했다.

n_list = sorted(n_list)
print(n_list)
# 길이가 m이고 0인 리스트 만들기
isThere = [0 for i in range(m)]
for m_num in m_list:
    for n_num in n_list:
        if n_num == m_num:
            isThere[m_list.index(m_num)] = 1
            break

for i in isThere:
    print(i)

 

 

그 다음 시간을 줄이기 위해 이진 탐색법을 이용해서 

중간값에서 크기 비교해서 찾는 nlogn을 이용했다.

 

하지만 함수 안에 리스트를 sort하는 함수가 있었고 이 함수는 n의 시간복잡도를 가지므로

다시 n^2이 되었다.

 

따라서 sort하는 함수를 for 루프 전에 미리 해주고,

len 함수는 O(1)이라고 한다. (이미 정해진 값을 불러오는 함수)

 

결과가 틀렸다고 나와서 다시 한번 원인을 찾았다.

바로 리스트의 각 원소별로 for문을 돌렸기 때문

따라서 

5 5 1 2 3 2 5 1 2 8 1 9

 

같은 예시에는 1 1 0 0 0이 나올 수 밖에 없다.

뒤에 1은 이미 앞에 1에 index 값을 읽다가 묻히기 때문..

 

for num in range(m_list):

그러므로 원소별로 for문을 돌릴 것이 아니라

인덱스 별로 돌려야 한다.

for i in range(m):

요렇게!

# data 입력
n = int(input())
n_list = list(map(int, input().split()))
# target 입력
m = int(input())
m_list = list(map(int, input().split()))

def binary_search(target, data):
    start = 0
    end = len(data) - 1

    while start <= end:
        mid = (start + end) // 2
        if data[mid] == target:
            # return mid
            return 1
        elif data[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return 0


# 길이가 m이고 0인 리스트 만들기
isThere = [0 for i in range(m)]
exist = 0
n_list.sort()
for i in range(m): # 타겟 서칭
    exist = binary_search(m_list[i], n_list)
    if isThere[i] != 1:
        isThere[i] += exist

for i in isThere:
    print(i)