글 읽기 - python3) 어떻게 해야 시간복잡도가 줄어들까요? ㅠㅠ

kravi 4년 전 0

꽤 오랫동안 고민하는중인데

도저히 진전이 안 보여서 글을 남깁니다 ㅜㅜ

자그마한 힌트나 공부해야할 알고리즘 이름이라도 알려주시면 감사하겠습니다...

덧)

append하지말고 미리 리스트를 만들어놓고 값을 입력하면 시간을 좀 아낄 수 있을까요?

n = int(input())
lst = [False for i in range(n)]
lsti = [int(i) for i in input().split()]
lsts = []
for i in range(n):
    idx = lsti[i] - 1
    lst[idx] = not lst[idx]
    lsts.append(sum(lst))
print(max(lsts))

jh05013 4년 전 1

sum(lst)는 lst를 쭉 훑어 보면서 합을 구하기 때문에 비효율적입니다. 매 루프마다 합이 정확히 1 증가하거나 감소한다는 점을 이용해 보세요.

kravi 4년 전 0

감사합니다 ㅋㅋㅋ

사실 어젯밤에 자면서 생각하다가 그 생각이 떠올라서 일어나자마자 해보니까 되더라구요

답변 감사합니다

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

문제

문제

출처

ICPC

python3) 어떻게 해야 시간복잡도가 줄어들까요? ㅠㅠ

kravi 4년 전 0

jh05013 4년 전 1

kravi 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말