글 읽기 - 시간 초과가 뜨는 이유를 모르겠습니다.....

yang000501 2년 전 0

문제에 대한 해당 코드를 제출하면 시간초과가 표시됩니다.

제가 생각하기에는 해당 알고리즘이 O(n)이라고 생각하는데 시간초과가 되는 이유를 모르겠습니다.

코드에서 수정해야 할 부분이나 제가 잘못알고 있는 부분이 있으면이 조언부탁드립니다.^^

import sys

str = sys.stdin.readline()
str = str.strip()

# ppap 있는 경우 p로 치환
while 'PPAP' in str:
  str = str.replace('PPAP', 'P')

if str == 'P':
  print("PPAP")
else:
  print("NP")

ai4youej 2년 전 0

1. 'PPAP' in str 은 O(n)입니다.

2. 사실 저 코드는 O(n^2)처럼 보입니다. 8번째 줄 str = str.replace('PPAP', 'P') 또한 O(n)입니다.

3. PPAP가 엄청 겹친다면 Worst Case에서는 while 문이 n번에 비례해서 돌 것이기 때문에 이런 경우는 O(n^2)입니다.

4. 스택을 이용해서 푸는 방법을 생각해보세요.

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

문제

문제

출처

ICPC

시간 초과가 뜨는 이유를 모르겠습니다.....

yang000501 2년 전 0

ai4youej 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말