[Python] 백준 1759 & 백준 1987

# 백준 1759
def solution(depth, index, word):
    if depth == L:
        vo, co = 0, 0
        for w in word:
            if w in 'aeiou':
                vo += 1
            else:
                co += 1
        if vo >= 1 and co >= 2:
            print(word)
            return

    for i in range(index, C):
        solution(depth+1, i+1, word + memo[i])

L, C = map(int, input().split())
memo = list(input().split())
memo.sort()
solution(0, 0, "")

#1987 알파벳

import sys

input = sys.stdin.readline
n, m = map(int, input().split(' ')) # 세로, 가로
graph = [list(map(str, input().rstrip())) for _ in range(n)]
queue = set()

d_row = [0, -1, 0, 1]
d_col = [1, 0, -1, 0]

def bfs():
    word = graph[0][0]
    queue.add((0, 0, word))
    global result
    while queue:
        x, y, word = queue.pop()
        result = max(result, len(word))
        for i in range(4):
            nx = x + d_row[i]
            ny = y + d_col[i]
            if nx <0 or ny < 0 or nx> n-1 or ny > m-1:
                continue
            if graph[nx][ny] in word:
                continue
            queue.add((nx, ny, word+graph[nx][ny]))

result = 0
bfs()
print(result)

queue = deque()로 했더니 시간초과ㅠㅠ

set으로 했더니 성공

 

 

📝 queue vs set

• deque의 시간복잡도는 O(1)
• set의 시간복잡도도 O(1)

 

하지만 queue은 중복을 허용하기 때문에 중복된 값 넣어도 계산해서 시간초과남

그래서 set으로 중복 허용하지않으면 시간이 단축된다.