글 읽기 - 파이썬 메모리..

kimwinner90 4년 전 0

메모리초과 어떻게 해결 하나요;;?? 이전 글들만 봐선 잘 모르겠어요 ㅠㅠ

import sys

N, K = map(int, sys.stdin.readline().split(' '))
nums = list(map(int, sys.stdin.readline().split(' ')))
K = K - 1

def partition(arr, first, last):
    lessPoint = first - 1
    checkPoint = first
    pivot = arr[last]  
    for i in range(last - first):
        if arr[checkPoint] >= pivot:
            checkPoint += 1
        else:
            lessPoint += 1
            arr[checkPoint], arr[lessPoint] = arr[lessPoint], arr[checkPoint]
            checkPoint += 1

    pivotIdx = lessPoint + 1
    arr[last], arr[pivotIdx] = arr[pivotIdx], arr[last]

    return pivotIdx


def quick_selection(arr, first, last, n):
    if first < last:
        pivot = partition(arr, first, last)
        if pivot == n:
            print(arr[pivot])
        elif pivot < n:
            quick_selection(arr, pivot + 1, last, n)
        else:
            quick_selection(arr, first, pivot - 1, n)


quick_selection(test, 0, len(test) - 1, n)

jh05013 4년 전 3

이렇게 한 줄에 500만 개 정도의 수가 주어지는 문제는 파이썬에게 불리합니다. 기본적으로 한 줄씩 읽는데, 그걸 다시 분리하고 int를 씌우느라 1000만 개는 기본으로 넘어가기 때문입니다. 아래처럼 몇 글자 단위로 읽는 건 가능합니다.

from sys import stdin
def read():
    while 1:
        s = stdin.read(100000)
        if not s: return
        while s[-1] != ' ':
            extra = stdin.read(1)
            if not extra: break
            s+= extra
        yield from map(int, s.split())

khris 4년 전 1

이 문제에 한정해서 좀 더 간단한 답도 있습니다. 물론 메모리 제한이 더 빡세다면 위의 jh05013님이 설명하신 방법으로 풀어야합니다. 대량의 데이터를 처리할때는 위와 같은 방법이 정석이기도 하고요.

sorted, map, reduce 같은 함수와 list comprehension([int(x) for x in input().split()] 같이 생긴 것들)은 원본을 전혀 건드리지 않고 새 사본을 생성한다는것을 항상 염두에 두세요. 원본이 새 사본 데이터를 생성하는 라인을 지나면 사라진다 해도 별도의 최적화 같은 것은 없습니다.

이 문제는 아래와 같은 코드로 in-place 변환을 해 주는것만으로도 메모리 제한을 우회할 수 있습니다.

nums = sys.stdin.readline().split(' ')
for i in range(len(nums)):
    nums[i] = int(nums[i])

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

문제

문제

출처

ICPC

파이썬 메모리..

kimwinner90 4년 전 0

jh05013 4년 전 3

khris 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말