ZEROONE 문제 질문드립니다.(파이썬)

  • mongsiry014
    mongsiry014

    ZERO ONE 문제 파이썬 코드를 여러번 수정해보았는데
    매번 시간제한이네요 ㅠ.ㅠ
    의문점이 드는건 작성한 코드가 연산을 그리 많이 안하는 것 같은데 2000ms 내에 처리가 되지 않는군요.

    while문이 두개인데 최악의 경우 첫번째 while문은 백만번 실행되고 두번째 while문은 10만번 실행됩니다. 도대체 어디서 시간을 그리 많이 잡아 먹는걸까요?ㅠ

    import sys
rl = lambda: sys.stdin.readline()

S = rl().strip()
n = int(rl())

L = [0]*len(S)
i = 1
while i < len(S) :
    if S[i] == S[i-1] :
        L[i] = L[i-1]
    else :
        L[i] = L[i-1]+1
    i+= 1

i = 0
res = ""
while i < n :
    x, y = [int(k) for k in rl().strip().split(' ')]
    if L[x] == L[y] : res += "Yes\n"
    else : res += "No\n"
    i += 1
res = res[:-1]
print(res)

    코드 설명 :
    S가 입력 받은 수열입니다.
    L[i]가 의미하는것은 수열 S에서 0부터 i번째까지 S[k] 와 S[k+1]이 다른 경우의 개수입니다.
    즉 L[x]와 L[y]가 같다면 S[x:y+1]은 모두 0 또는 1로 이루어진 수열이라는 뜻입니다.


    10년 전
2개의 댓글이 있습니다.
  • mongsiry014
    mongsiry014

    c코드로 작성하니까 통과네요 ㅠ.ㅠ


    10년 전 link
  • Kureyo
    Kureyo

    이 문제는 입출력이 커서 그런가보네요ㅠ


    10년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.