글 읽기 - 파이썬 10816번

sd1010 1년 전 0

딕셔너리 이용하지 않고 이분탐색으로 가장 왼쪽 인덱스, 오른쪽 인덱스를 구해서 갯수를 카운트하고 싶은데 시간초과가 계속해서 납니다. 구글링을 통해 알아낸 upperbound, lowerbound를 보고 비슷하게 따라했는데 어느 부분에서 시간초과가 나는지 모르겠습니다. 설명이나 시간초과가 나는 예제부탁드립니다.

import sys

n=int(sys.stdin.readline().rstrip())
n_num=list(map(int,sys.stdin.readline().split()))
m=int(sys.stdin.readline().rstrip())
m_num=list(map(int,sys.stdin.readline().split()))
result=[]

n_num.sort()

for i in m_num:
    left=0
    right=len(n_num)-1
    mid=(left+right)//2
    # print('목표값',i,left,right,mid)
    # print(n_num)
    cnt=1
    while (True):
        mid=(left+right)//2
        if n_num[left]<=i and i<=n_num[mid]:
            right=mid
        elif n_num[mid]<i and i<=n_num[right]:
            left=mid+1
        else:
            left=-1
            break
        if left>=right:
            if n_num[left]==i:
                pass
            else:
                left=-1
            break

    final_left=left
    
    left=0
    right=len(n_num)-1
    mid=(left+right)//2
    while (True):
        mid=((left+right)//2)+1
        
        if n_num[mid]<=i and i<=n_num[right]:
            left=mid
        elif n_num[left]<=i and i<n_num[mid]:
            right=mid-1
        else:
            right=-1
            break
        if left>=right:
            if n_num[right]==i:
                pass
            else:
                right=-1
            break
    final_right=right
    # print(final_left,final_right)

    if final_left==-1 or final_right==-1:
        result.append(0)
    else:
        result.append(final_right-final_left+1)

print(result)

sd1010 1년 전 0

질문자입니다...

신기하게 python3가 아닌 PyPy3를 선택해서 돌려보니 정답처리되네요.

무슨 차이인지 잘 모르겠지만 저처럼 파이썬으로 시간초과나는 인원은 PyPy3 이용해보시면 좋을 것 같습니다.

seawon0808 1년 전 1

python은 pypy보다 시간을 많이 사용하지만 pypy는 python보다 메모리를 더 많이 사용합니다.

그래서 문제 풀이 방식은 맞는 것 같은데 시간 초과가 날 때는 pypy로도 제출해 보시면 좋습니다.

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

문제

문제

출처

ICPC

파이썬 10816번

sd1010 1년 전 0

sd1010 1년 전 0

seawon0808 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말