[Python]BAEKJOON 10816번 숫자카드 2

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

10816번: 숫자 카드 2

 

실패 Try 1

import sys
input = sys.stdin.readline 
N = int(input())
lst = list(map(int,input().split()))
lst.sort()
int(input())
flst = list(map(int,input().split()))
res = []
def bin(i,lst,left,right,cnt):
    if left > right: return 0
    mid = (left+right)//2
    if lst[mid] == i: 
        cnt+=1
        bin(i,lst, left,mid-1,cnt)
        bin(i,lst, mid+1,right,cnt)
        return cnt
    elif lst[mid] > i: return bin(i,lst, left,mid-1,cnt)
    elif lst[mid] < i: return bin(i,lst, mid+1,right,cnt)

for i in flst:
    cnt = 0
    left = 0
    right = N-1 
    res.append(bin(i,lst,left,right,cnt))
print(*res)

 

주어진 예제에 대해 다음과 같이 출력하기 때문.(숫자카드 1 문제코드와 다를 바가 없음.)

 

1 0 0 1 1 0 0 1

 

실패 Try2 - 'pypy3, python3 모두 시간초과' count() 함수 이용 

import sys
input = sys.stdin.readline 
N = int(input())
lst = list(map(int,input().split()))
lst.sort()
int(input())
flst = list(map(int,input().split()))
res = []
def bin(i,lst,left,right):
    if left > right: return 0
    mid = (left+right)//2
    if lst[mid] == i: 
        return lst[left:right+1].count(i)
    elif lst[mid] > i: return bin(i,lst, left,mid-1)
    elif lst[mid] < i: return bin(i,lst, mid+1,right)

for i in flst:
    left = 0
    right = N-1 
    res.append(bin(i,lst,left,right))
print(*res)

 

'성공!' - 시간초과 극복 Sol0 - 577B 1872ms

그대로 count()함수를 이용했고, 바뀐건 리스트에 append()시키지 않고 딕셔너리의 키와 value를 이용해, 

저장된 값이 있으면 불러오고 없으면 0을 출력하도록 했다. 1872ms로, 상당히 시간이 오래 걸렸는데, 이를 최대한 줄일 수 있는 방법을 알아보자. 

import sys
input = sys.stdin.readline 
N = int(input())
lst = list(map(int,input().split()))
lst.sort()
int(input())
flst = list(map(int,input().split()))
dic = {}
def bin(i,lst,left,right):
    if left > right: return 0
    mid = (left+right)//2
    if lst[mid] == i: 
        return lst[left:right+1].count(i)
    elif lst[mid] > i: return bin(i,lst, left,mid-1)
    elif lst[mid] < i: return bin(i,lst, mid+1,right)
for i in lst:
    left = 0
    right = N-1 
    if i not in dic:dic[i] = bin(i,lst,left,right) 
for i in flst:
    print(dic[i] if i in dic else 0 ,end = ' ')

 

Sol 1 - 581B 2032ms

반복되는 숫자의 개수를 따로 센 후, 그 개수 값을 딕셔너리에 저장, 

lst[mid]==i 인 경우에 dic[i]값을 그 자체를 반환한다. 

 

import sys
input = sys.stdin.readline 
N = int(input())
lst = sorted(map(int,input().split()))   ## 선 정렬. 내장함수 sorted()는 정렬 된 리스트를 결과로 반환한다.
int(input())
flst = list(map(int,input().split()))
dic = {}
def bin(i,lst,left,right):
    if left > right: return 0
    mid = (left+right)//2
    if lst[mid] == i:
        return dic[i]
    elif lst[mid] > i: return bin(i,lst, left,mid-1)
    elif lst[mid] < i: return bin(i,lst, mid+1,right)
for i in lst:
    if i in dic:dic[i] += 1                                        
    else: dic[i] = 1

for i in flst:
    left = 0
    right = N-1 
    print(bin(i,lst, left,right),end = ' ')

 

 

Sol2 - 340B 676ms

사실 Sol1은 이분탐색과 해시 알고리즘을 동시에 사용한 코드다. 

'반복되는 숫자의 개수를 따로 센 후, 그 개수 값을 딕셔너리에 저장'하는 방식이 해시 알고리즘이다.

하지만 조금 단순하게 생각해보면, 이분탐색을 쓰지 않고 해시 알고리즘만을 이용해서 이 문제를 풀 수 있다는 사실을 알 수 있다. 이분탐색은 오름차순으로 정렬된 데이터셋에 대해, mid(중앙값)을 기준으로 내가 찾고자 하는 값의 위치를 산정하는 방식이다. 선형탐색(시간복잡도 O(N))에 비해 이분탐색(시간복잡도 O(log(N))의 효용성이 좋기에 사용하는 거지, 쓰지 않아도 되면 안쓰는 게 시간복잡도 측면에서 효율적이다. 해시 함수를 사용하면 정렬할 필요가 없고, 반복된 빈도수에 따라 숫자의 개수 값을 딕셔너리에 저장하고 바로 불러오기에 압도적으로 시간을 줄일 수 있다. 

아래 그림을 참고하라. 

밑줄 친 두 코드는 각각 Sol1과 Sol2를 pypy3로 제출한 것이다.(코드길이 581B(아래)가 Sol1, 340B(위)가 Sol2.)

Sol1은 이분탐색과 해시를 모두 이용했고, Sol2는 해시만 사용했다. 각각 걸린 시간은 2032ms와 676ms이므로, Sol1의 실행시간이 Sol2 실행시간의 3배가 넘는 것을 확인할 수 있다. 

import sys
input = sys.stdin.readline 
N = int(input())
lst = list(map(int,input().split()))
int(input())
flst = list(map(int,input().split()))
hashdic = {}
for i in lst:
    if i in hashdic:hashdic[i] += 1                                        
    else: hashdic[i] = 1
for i in flst:
    print(hashdic[i] if i in hashdic else 0, end=' ')