글 읽기 - python3 시간초과 관련 질문

kbpark9898 3년 전 0

이분탐색의 lower bound, upper bound를 구하는 코드를 작성했고, 파이썬의 bisect 라이브러리를 사용했습니다.

불필요한 이분탐색을 줄일수 있도록, lower bound를 구한 뒤 그 인덱스에 해당하는 배열 데이터와 target 데이터가 같지 않다면 upper bound를 구하는 이분탐색을 건너뛰는 방식으로 설계했습니다.

또한, product 함수의 실행 시간이 2중 for문에 비해 느리게 실행될 수 있다고 생각되어, 두개의 합 배열을 만드는 과정에서 2중 for문을 활용해봐도 시간초과는 똑같습니다.

어떻게하면 코드를 더 최적화할 수 있을까요??

추가1) pypy3로 제출해도 똑같이 시간초과가 뜹니다 ㅠㅠ

추가2) 단순한 이분탐색이 아닌, 딕셔너리를 같이 활용한 풀이로 해결했습니다.

import bisect
import sys
from itertools import product

#입력값 받기
k = int(input())
a=[]
b=[]
c=[]
d=[]

#product 함수 이용을 위한 인덱스 배열 형성
index=[i for i in range(k)]

#a, b, c, d 배열 제작
for i in range(k):
    q, w, e, r=map(int, sys.stdin.readline().split())
    a.append(q)
    b.append(w)
    c.append(e)
    d.append(r)

#이분탐색을 위한 a+b, -(c+d) 배열 
#2중 for문을 사용해 배열을 만들어도 똑같이 시간초과.
first_sum_data=[]
second_sum_data=[]
for prod in product(index, repeat=2):
    first_sum_data.append(a[prod[0]]+b[prod[1]])
    second_sum_data.append(-(c[prod[0]]+d[prod[1]]))

# a+b값을 -(c+d)배열에서 찾기위해 -(c+d) 배열을 정렬
second_sum_data.sort()
count=0

#이분탐색을 통해 (bisect) lower, upper 바운드를 계산. 
for i in first_sum_data:
    left=bisect.bisect_left(second_sum_data, i)
    #second_sum_data[left] 값이 i와 다르다면 i 값이 second_sum_data에 없다는 뜻이므로
    #upper bound를 계산하기 위한 이분탐색을 건너뜀
    if second_sum_data[left]!=i:
        continue
    right=bisect.bisect_right(second_sum_data, i)
    count+=(right-left)
print(count)

herdson 3년 전 1

c++ lower_bound와 upper_bound를 이용한 솔루션으로 11초가 소요되었으니 파이썬은 어림도 없을 것 같습니다.

ehdrmsl2001 3년 전 0

파이썬으로는 맞은 분이 아예 없습니다... pypy로 제출해보세요

kbpark9898 3년 전 0

pypy3로 제출해도 똑같이 시간초과입니다 ㅠㅠ

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

문제

문제

출처

ICPC

python3 시간초과 관련 질문

kbpark9898 3년 전 0

herdson 3년 전 1

ehdrmsl2001 3년 전 0

kbpark9898 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말