글 읽기 - [파이썬 , 부등호] 메모리초과가 발생합니다.

evergreening 4년 전 0

안녕하세요.

알고리즘을 시작한지 얼마 안된 초보입니다.

시간복잡도에 대한 이해는 조금씩 되는데

공간복잡도에 대한 이해가 잘 되지않아서 발생한 문제 같습니다.

결과는 제대로 출력되나 메모리 초과가 발생합니다.

기본적으로 최소값 숫자 리스트, 최대값 숫자 리스트를 저장하고

이 숫자들을 파이썬 내장함수 permutations를 이용하여 순열을 만들어 최소값을 체크하고자 했습니다.

그리고 첫번째 숫자와 그다음 숫자 사이의 부등호 방향이 맞으면 계속, 아니라면 break 를 하며

출력하고자 했습니다.

수정해야하거나 좀더 공부해보면 좋을 자료가 있다면 링크 부탁드립니다! ㅜ

감사합니다.

from itertools import permutations

k = int(input())
signList = list(map(str, input().split()))

minNums = [i for i in range(k + 1)]
maxNums = [i for i in range(9, 8 - k, -1)]

p1 = list(permutations(maxNums))
p2 = list(permutations(minNums))
    
def createList():
    #possible Num
    arr = [0] * k
    cnt = [0] * k 
    for j in range(k):
        for i in range(9):
            arr[j] = i


def find(p):
    for e in p:
        cnt = 0
        for i in range(k):  # 부등호 개수 + 1 = 최대 자리수.
            if signList[i] == '<':
                if e[i] < e[i + 1]:
                    cnt += 1
                    continue
                else:
                    break
            elif signList[i] == '>':
                if e[i] > e[i + 1]:
                    cnt += 1
                    continue
                else:
                    break
        if cnt == k:
            print(''.join([str(l) for l in e]))
            break    

jeenie145 3년 전 3

permutations를 쓰면 부등호를 고려하지 않고 모든 경우를 다 구하므로 메모리 초과가 발생합니다.

부등호를 고려하여 (앞뒤 크기를 고려하여) 조합을 만들어야 합니다.

dfs방법으로 푸는 것을 추천합니다.

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

문제

문제

출처

ICPC

[파이썬 , 부등호] 메모리초과가 발생합니다.

evergreening 4년 전 0

jeenie145 3년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말