글 읽기 - [Python] 시간초과의 이유를 모르겠습니다.

(追記) (追記ここまで)

[Python] 시간초과의 이유를 모르겠습니다.

25498번 - 핸들 뭘로 하지

dodobow 2년 전 0

BFS를 사용해 접근했습니다. 각 depth별 가장 사전순으로 뒤쪽인 글자들을 mx[depth]에 저장하고, 큐에서 pop한 원소 x가 해당 depth의 mx인 경우에만 탐색을 이어 진행했습니다. 모든 정점과 간선을 최대 1번 방문하고 문자열의 비교도 1글자의 비교만 일어나기에 시간복잡도가 O(N) 일 것이라 예상하고 풀이를 진행했지만 시간 초과를 받았습니다. 혹시 어떤 이유로 이런 문제가 발생하나요?

import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
s = input().strip()
graph = [[] for _ in range(n + 1)]
for _ in range(n - 1):
 a, b = map(int, input().split())
 graph[a].append(b)
 graph[b].append(a)
visit = [0] * (n + 1)
visit[1] = 1
mx = [''] * (n + 1)
mx[1] = s[0]
ans = ''
q = deque([1])
while q:
 x = q.popleft()
 if s[x - 1] != mx[visit[x]]:
 continue
 for i in graph[x]:
 if not visit[i] and s[i - 1] >= mx[visit[x] + 1]:
 visit[i] = visit[x] + 1
 mx[visit[i]] = s[i - 1]
 q.append(i)
for i in range(1, n + 1):
 if mx[i]:
 ans += mx[i]
print(ans)

댓글을 작성하려면 로그인해야 합니다.

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC