글 읽기 - 파이썬으로 해결하기

ky135 3년 전 0

기본적인 알고리즘은 다음과 같습니다.

1. List를 현재 값과 현재 index를 갖는 2차원 배열로 선언

2. List의 첫번째 원소에 값을 기준으로 내림차순 정렬

3. slice 기준에 따라 List[1]의 원소가 범위 내에있으면 count++

4. count가 찾고자하는 위치의 인덱스와 같아지면 break후 출력

-- zip 함수와 merge sort, 입력방식을 input에서 sys.stdin.readline() 등의 방법은 기존의 방식으로 시간초과를 해결하지 못해 나름 몇가지 바꿔본 방법들입니다.

zip 함수 대신 각각의 원소로 접근하여 [element, index]의 값을 갖는 List를 가져와 sort해도 2%를 넘어가지 못하고있습니다.

혹시 파이썬으로 푸신 분들 중 다음과 같은 방법으로 했을때 시간초과를 해결하는 방법에대해 조언 부탁드립니다.

import sys
def merge_sort(list):
    if len(list) <= 1:
        return list
    mid = len(list) // 2
    leftList = list[:mid]
    rightList = list[mid:]
    leftList = merge_sort(leftList)
    rightList = merge_sort(rightList)
    return merge(leftList, rightList)

def merge(left, right):
    result = []
    while len(left) > 0 or len(right) > 0:
        if len(left) > 0 and len(right) > 0:
            if left[0][0] <= right[0][0]:
                result.append(left[0])
                left = left[1:]
            else:
                result.append(right[0])
                right = right[1:]
        elif len(left) > 0:
            result.append(left[0])
            left = left[1:]
        elif len(right) > 0:
            result.append(right[0])
            right = right[1:]
    return result

case = list(map(int, sys.stdin.readline().split()))

List = list(map(int, sys.stdin.readline().split()))
Index = [k for k in range(len(List))]
List = list(zip(List, Index))

List.sort(key = lambda x : x[0])
for _ in range(case[1]):
    test = list(map(int, sys.stdin.readline().split()))
    cnt = 0
    for element in List:
        if element[1] < test[1] and element[1] >= test[0]-1:
            cnt+=1
            if cnt == test[2]:
                print(element[0])
                break

pichulia 3년 전 0

O(QN)의 풀이로는 시간초과를 피할 수 없습니다.

각 함수의 결과값을 구하기 위해 배열을 전부 순회하는 방법을 사용했다면

아무도 놀라지 않았을 것입니다.

pichulia 3년 전 0

엥... O(QN)이 통과된다는 소식을 듣고왔습니다.. 어째서.....

ky135 3년 전 0

자바에서는 동일한 방법으로 통과함을 확인할 수 있었고 구글링 시에도 다음과같은 방법으로 통과했다는 글들을 몇개 볼수있었습니다.ㅠㅠ

djm03178 3년 전 1

Python 3로는 아마도 불가능하지 않나 싶고, PyPy로 아주 잘 최적화하면 통과할 수 있는 것 같습니다.

파이썬이 C나 C++에 비해 수십 배 느린 반면에 시간 보너스는 *3+2초밖에 받지 못한다는 점을 생각하셔야 합니다. 애초에 그 풀이가 의도된 문제라고 생각되지 않고, C나 C++로도 시간이 상당히 많이 걸리는 편인데 그것이 파이썬으로도 통과될 것으로 믿지 않는 것이 좋습니다.

ky135 3년 전 0

조언 감사합니다:)

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

문제

문제

출처

ICPC

파이썬으로 해결하기

ky135 3년 전 0

pichulia 3년 전 0

pichulia 3년 전 0

ky135 3년 전 0

djm03178 3년 전 1

ky135 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말