글 읽기 - 두 코드의 시간복잡도

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

두 코드의 시간복잡도

11478번 - 서로 다른 부분 문자열의 개수

tlswnsgh0624 9달 전 0

1번 코드는 정답인데 2번 코드는 시간초과로 정답이 아니네요.

s를 list로 두는 것과 for 문 안 조건문이 시간을 그렇게나 많이 잡아먹나요??

#1번: 정답
import sys
input = sys.stdin.readline
# list가 str보다 메모리 사용량이 많음
s = input().rstrip()
ps = set()
for i in range(len(s)+1):
 for j in range(len(s)+1):
 if s[i:j]: ps.add(s[i:j])
print(len(ps))
#2번: 시간초과
import sys
input = sys.stdin.readline
s = list(input().rstrip())
ps = set()
for i in range(len(s)+1):
 for j in range(len(s)+1):
 if bool(s[i:j]) == True: ps.add(str(s[i:j]))
print(len(ps))

munji123 9달 전 1

str함수가 배열에서 문자열로 만드는 과정에서 오버헤드가 큰 것 같습니다

간략하게만 봐도 0부터 N까지 N(N+1)/2만큼 접근을 해야되네요

tlswnsgh0624 9달 전 0

그 외의 if bool이나
s를 입력받아서 배열로 만드는 건 크게 상관이 없다는 의미로 받아들여도 될까요?

댓글 감사합니다!

munji123 9달 전 1

탐색범위를 len(s)까지만 하면 if로 확인이 필요없습니다. 마찬가지로 배열로 만들 필요도 없죠

tlswnsgh0624 9달 전 0

넵! 감사합니다!!~

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

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

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO

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

한국어 | English (Beta)