[코드 분석 요청] ZEROONE 문제입니다.

  • 맥커터
    맥커터

    python 3으로 짠 코드입니다.

    알고리즘은 한번 데이터를 스캔하면서
    값이 변할 때마다 누적된 값을 operated _ data에 채워주는 방식이구요
    왜 시간 초과가 나는지 모르겠네요;
    한번만 O(N)이고, 각각의 케이스에 대해서는 O(1)인데 말이죠.
    CPP로 하면 시간초과가 안날까요?
    아래는 코드입니다.

    default_data = list(input())
operated_data = list()

operated_data.append(0)
count = 0
length = len(default_data)
for i in range(1, length):
    if(default_data[i - 1] != default_data[i]):
        count += 1

    operated_data.append(count)

n = int(input())

for i in range(n):
    index_begin, index_end = map(int, input().split())

    if(operated_data[index_begin] == operated_data[index_end]):
        print("Yes")
    else:
        print("No")


    8년 전
2개의 댓글이 있습니다.
  • JongMan
    JongMan

    네 시간이 꽤 빡빡해서; 파이썬으론 안 풀릴 가능성이 높아 보이네요.


    8년 전 link
  • 맥커터
    맥커터

    다른 분이 Python으로 푼 걸 보니
    저는 append를 사용해서 list에 추가해주었고
    그 분은 list를 생성하면서 값을 채웠다 정도인데

    아마 list가 linked list가 아닌 vector 형식으로 이루어져서
    append 시에 시간이 오래 걸린 것 같네요.

    답변 감사합니다.


    8년 전 link

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