[백준][python]1920.수찾기 - 이진탐색

아래의 문제는 '백준'의 알고리즘 문제 내용이며 코드는 직접 푼 내용입니다.

---

 

1920.수찾기 

문제 및 입출력 

입출력예시 

---

나의시도

그냥 단순하게 문자열안에서 검색하도록 in 을 썼다. 

그런데 다시보니 자연수의 범위가 10만까지이다. 그래서 시간초과가 났다.

 

결과 (시간초과)

import sys
input=sys.stdin.readline
n=int(input())
n_list=list(map(int,input().split()))

m=int(input())
m_list=list(map(int,input().split()))

for m in m_list:
    if m in n_list:
        print("1")
    else:
        print("0")

 

결과2 (출력초과)

혹시 몰라서 문자열매칭 패키지인 re를 써서도 탐색해봤다. 

이럴 경우 문자열매칭을 하려고 리스트가 아니라 문자열로 변환해서 확인을 했다.

그런데 리턴값도 요구사항이랑 같은데 출력초과 오류라고 한다...

그래서 리스트가 아니라 문자열로 변환해서 읽어서 그런건가 이유는 잘 모르겠따ㅠㅠ 

import re
import sys
input=sys.stdin.readline
n=int(input())
n_list=''.join(input().split())

m=int(input())
m_list=''.join(input().split())
for m in m_list:
    if re.search(m,n_list):
        print("1")
    else:
        print("0")

---

풀이과정

이분탐색(이진탐색)을 이용해서 조금더 효과적으로 탐색할 수 있었다. 

비교해야하는 문자의 길이가 10만까지 길어질 수 있어서 반씩 계속 나누어서 확인을 하는 방법이다. 

import sys
input=sys.stdin.readline

n=int(input())
n_list=list(map(int,input().split()))
n_list=sorted(n_list)

m=int(input())
m_list=list(map(int,input().split()))

def binary_search(element,some_list,start=0,end=None):
    if end==None:
        end=len(some_list)-1
    if start>end:
        return 0

    mid = (start+end) //2

    if element == some_list[mid]:
        return 1
    elif element < some_list[mid]:
        end = mid-1
    elif element > some_list[mid]:
        start = mid+1
    return binary_search(element,some_list,start,end)

for i in range(len(m_list)):
    print(binary_search(m_list[i],n_list))

 

또는 그냥 간단하게 dict를 사용해서 확인할 수도 있었다.

그리고 이진탐색방법과 dict방식의 메모리사용량은 비슷하지만 수행시간에서 차이가 있었다.

이진탐색방법은 916ms, dict사용방법은 240ms

#dict사용 : 메모리 50352, 시간 240ms
import sys
input=sys.stdin.readline
n=int(input().rstrip())
n_list=list(map(int,input().split()))

n_dict={}
for val in n_list:
    n_dict[val]=1
#print(n_dict)

m=int(input())
m_list=list(map(int,input().split()))
for val in m_list:
    try:
        print(n_dict[val])
    except KeyError:
        print(0)

 

배운점

• 길이가 긴 (10만이상) 문자열을 탐색을 해야할경우, 일반적인 문자열함수(in,find)는 시간초과
• 길이가 긴 (10만이상) 문자열을 탐색을 해야할경우, 문자열탐색 패키지(re, search)를 사용할 수 도 있다.
• 길이가 긴 (10만이상) 문자열을 탐색을 해야할경우, 이진탐색찾을 수 있다!
• 사실 그냥 비교해야할 리스트들을 dict의 key로 지정해두고, 그 key가 있는지 비교하는게 더 효율적이다. 

---

참고 

참고한 블로그 링크

https://velog.io/@sch804/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EB%B0%B1%EC%A4%80-1157%EB%B2%88-%EB%8B%A8%EC%96%B4-%EA%B3%B5%EB%B6%80