[BOJ/백준] 14226 이모티콘

# 이모티콘 S
# 모두복사
# 클립보드 모두 붙이기
def bfs():
    global S
    stack = [(1,0,0)]
 
    visited = []
    while stack:
        emo_cnt,clip_cnt,second = stack.pop(0)
        if (emo_cnt,clip_cnt) in visited:
           continue 
        visited.append((emo_cnt,clip_cnt))
        if emo_cnt == S:
            break
        stack.append((emo_cnt,emo_cnt,second+1))
        if emo_cnt and clip_cnt:
            stack.append((emo_cnt+clip_cnt,clip_cnt,second+1))
        if emo_cnt > 2:
            stack.append((emo_cnt-1,clip_cnt,second+1))
 
    return second
 
 
S = int(input())
 
 
print(bfs())

기본적으로 bfs를 이용해서 풀었다.

bfs를 이용해서 각 단계마다, 추가가 될 수 있으면 추가를 해주는 방식으로 했다.

하지만 List에서 in을 써서 찾는 방식은 시간복잡도가 커서 오래걸려서 다른 방법으로 한번 더 풀었다.

 

 

 
 
S = int(input())
 
Set_emo_clip = set()
Set_emo_clip.add((1,0))
flag = False
time = 0
while True:
    time += 1
    temp_set = set()
    for emo_cnt,clip_cnt in Set_emo_clip:
        if (emo_cnt,emo_cnt) not in Set_emo_clip:
            temp_set.add((emo_cnt,emo_cnt))
        if (emo_cnt+clip_cnt,clip_cnt) not in Set_emo_clip:
            temp_set.add((emo_cnt+clip_cnt,clip_cnt))
            if emo_cnt+clip_cnt == S:
                flag = True
                break
        if emo_cnt > 0 and (emo_cnt-1,clip_cnt) not in Set_emo_clip:
            temp_set.add((emo_cnt-1,clip_cnt))
            if emo_cnt-1 == S:
                flag = True
                break
    if flag:
        break
    Set_emo_clip = Set_emo_clip | temp_set
print(time)

set가 dictionary는 List보다 해당 값이 존재하는지 판별하는데 시간이 더 적게 걸리므로, set과 dictionay형태를 쓰거나,

현재 이모티콘의 개수와 클립보드의 개수를 가지고 방문여부를 판단하니, 적당히 큰 2차원배열를 만들어, 방문여부를 체크하는 것도 한 방식일 것 같다.

 

 

set, list not in 비교

 

import time
 
list_time = time.time()
a = []
 
for k in range(100000):
    a.append(k)
    if k not in a:
        pass
print(f'list 추가 및 in 판단 시간 : {time.time()-list_time}')
 
set_time = time.time()
 
b = set()
 
for k in range(100000):
    b.add(k)
    if k not in b:
        pass
 
print(f'set 추가 및 in 확인 시간 : {time.time()-set_time}')

좀 부정확하겠지만, not in을 판별하는 과정을 추가하는 순간 시간차이가 확 나는걸 알 수 있다.