[백준]숫자 카드 2
링크 : 문제 바로가기
시도1
import sys
n=int(sys.stdin.readline().rstrip())
n_num=list(map(int,sys.stdin.readline().split()))
m=int(sys.stdin.readline().rstrip())
m_num=list(map(int,sys.stdin.readline().split()))
result=[]
for i in m_num:
cnt=0
for j in n_num:
if i==j:
cnt+=1
result.append(cnt)
print(result)
간단하게 for 2중문을 돌면서 완전탐색하면 된다는 생각으로 다음과 같은 코드를 작성했다. 하지만 각 리스트의 범위가 ( 1 ≤ N,M ≤ 500,000 )로 최악의 경우 500000x500000 번의 탐색을 하게 되어 시간초과가 발생했다.
시도2
import sys
n=int(sys.stdin.readline().rstrip())
n_num=list(map(int,sys.stdin.readline().split()))
m=int(sys.stdin.readline().rstrip())
m_num=list(map(int,sys.stdin.readline().split()))
result=[]
for i in m_num:
result.append(n_num.count(i))
print(result)
for 2중문 대신 count함수를 사용하려 했지만, 알고보니 count함수 또한 리스트를 모두 훑으며 탐색하는 알고리즘을 사용했다. 그래서 역시나 시간초과가 발생했다.
시도3
import sys
n=int(sys.stdin.readline().rstrip())
n_num=list(map(int,sys.stdin.readline().split()))
m=int(sys.stdin.readline().rstrip())
m_num=list(map(int,sys.stdin.readline().split()))
result=[]
n_num.sort()
for i in m_num:
l=len(n_num)
start=0
end=l-1
mid=(end+start)//2
while True:
v1=0
if n_num[start]==i:
v1=start
break
if n_num[mid]==i:
v1=mid
break
if n_num[end]==i:
v1=end
break
if n_num[start]<i and i<n_num[mid]:
end=mid-1
start+=1
mid=(start+end)//2
elif n_num[mid]<i and i<n_num[end]:
start=mid+1
end-=1
mid=(start+end)//2
else:
v1="없음"
break
if start>=end:
v1="없음"
break
l_v1=v1
r_v1=v1
if v1=="없음":
v2=0
else:
while l_v1!=-1 and n_num[l_v1]==n_num[v1]:
l_v1-=1
l_v1+=1
while r_v1!=l and n_num[r_v1]==n_num[v1]:
r_v1+=1
r_v1-=1
v2=r_v1-l_v1+1
result.append(v2)
print(result)
sort함수를 이용해 먼저 N개의 정수를 정렬하고, for문으로 M개의 정수를 각각 정렬된 N개 정수 리스트에서 이분 탐색을 이용해 찾으려고 했지만 시간초과가 발생했다. sort함수는 timsort라는 알고리즘을 사용해 시간복잡도가 O(n^2)이 아니라 O(nlog(n))이 나온다고 알고 있는데, 어디서 시간초과가 발생하는지 모르겠다.
시도4( 답은 맞음 )
import sys
from collections import Counter
n=int(sys.stdin.readline().rstrip())
n_num=list(map(int,sys.stdin.readline().split()))
n_num_count=Counter(n_num)
m=int(sys.stdin.readline().rstrip())
m_num=list(map(int,sys.stdin.readline().split()))
result=[]
for target in m_num:
if n_num_count.get(target)==None:
result.append(0)
else:
result.append(n_num_count.get(target))
for i in result:
print(i,end=' ')
시각을 아예 바꿔 Counter라이브러리를 이용해 딕셔너리 구조로 값들에 대한 횟수를 저장해 이용하는 방식을 이용했다. 하지만 문제의 의도 자체가 정렬과 이분 탐색을 이용하는 것이므로 해당 알고리즘을 이용해 푸는 방식을 더 생각해봐야한다.
시도5
import sys
n=int(sys.stdin.readline().rstrip())
n_num=list(map(int,sys.stdin.readline().split()))
m=int(sys.stdin.readline().rstrip())
m_num=list(map(int,sys.stdin.readline().split()))
result=[]
n_num.sort()
for i in m_num:
left=0
right=len(n_num)-1
mid=(left+right)//2
# print('목표값',i,left,right,mid)
# print(n_num)
cnt=1
while (True):
mid=(left+right)//2
if n_num[left]<=i and i<=n_num[mid]:
right=mid
elif n_num[mid]<i and i<=n_num[right]:
left=mid+1
else:
left=-1
break
if left>=right:
if n_num[left]==i:
pass
else:
left=-1
break
final_left=left
left=0
right=len(n_num)-1
mid=(left+right)//2
while (True):
mid=((left+right)//2)+1
if n_num[mid]<=i and i<=n_num[right]:
left=mid
elif n_num[left]<=i and i<n_num[mid]:
right=mid-1
else:
right=-1
break
if left>=right:
if n_num[right]==i:
pass
else:
right=-1
break
final_right=right
# print(final_left,final_right)
if final_left==-1 or final_right==-1:
result.append(0)
else:
result.append(final_right-final_left+1)
print(result)
찾고자 하는 값의 시작점, 끝점을 이분탐색을 각각 이용해 얻어내고 이 길이를 구하면 찾는 값이 몇개인지를 알 수 있다. 하지만 이 경우도 시간초과가 나온다… 이분 탐색만으로는 풀 수 없는 문제인 것 같다.
해결
해결이라기보단 시도5에서의 코드를 Python3가 아닌 PyPy3를 이용해 채점하니 정답처리가 되었다. 채점언어에 따라 메모리를 더 쓰거나, 시간을 더 쓰는 등의 이슈로 정답여부가 달라지는 듯하다.
알고리즘 : 자료 구조, 정렬,이분 탐색