[백준] 14888번 연산자 끼워넣기

시간초과 코드: permutations 이용

나란 사람, 멍청한 사람...  왜냐하면 이렇게 하면 시간초과 뜰 걸 알면서도 꾸역꾸역 함.. 그리고 결국 맞이한 시간초과

from itertools import permutations
n = int(input())
number = list(map(int, input().split()))
opnum = list(map(int, input().split()))
op = []
answer = []

for idx, i in enumerate(opnum):
    if idx == 0:
        for _ in range(i):
            op.append("+")
    elif idx == 1:
        for _ in range(i):
            op.append("-")
    elif idx == 2:
        for _ in range(i):
            op.append("*")
    elif idx == 3:
        for _ in range(i):
            op.append("/")

ops = list(permutations(op))
for op in ops:
    num = number[0]
    for i in range(1, len(number)):
        num = int(eval(str(num)+str(op[i-1])+str(number[i])))
    answer.append(num)

print(max(answer))
print(min(answer))

 

시간초과코드2. dfs로 풀었으나 또 시간초과

n = int(input())
number = list(map(int, input().split()))
opnum = list(map(int, input().split()))
op = []
answer = []

for idx, i in enumerate(opnum):
    if idx == 0:
        for _ in range(i):
            op.append("+")
    elif idx == 1:
        for _ in range(i):
            op.append("-")
    elif idx == 2:
        for _ in range(i):
            op.append("*")
    elif idx == 3:
        for _ in range(i):
            op.append("/")

maxnum = 0
minnum = 1000000000
def dfs(num, index, visited):
    global maxnum, minnum
    if index == (len(number)-1):
        maxnum = max(num, maxnum)
        minnum = min(num, minnum)
    for idx, i in enumerate(op):
        if visited[idx] == 0:
            num_ = int(eval(str(num)+i+str(number[index+1])))
            visited[idx] = 1
            dfs(num_, index+1, visited)
            visited[idx] = 0

def main():
    visited = [0] * len(op)
    num = number[0]
    dfs(num, 0, visited)
    print(maxnum)
    print(minnum)

main()

 

다른사람들의 풀이와 비교해보니 연산자들을 모두 하나씩 리스트에 넣어 처리한 것 (ex. [+, +, +, -, *, /, /] 이런 식)이 효율성에서 문제를 일으키는 것 같다. 일단 질문을 올려두었다. 내가 생각한 문제 때문인지가 맞는지 확인하기 위해... 

다른 사람들의 코드 (if문 4번) 과 함수 호출 횟수를 비교해봐야겠다. 

 

비교를 해봤는데 같다... 호출횟수가. 그렇다면 operator를 저장하는 문제일까? 저게 시간을 그리 많이 잡아먹는 것 같진 않은데...

분명 질문에서 처음 찾을 땐 안보였는데, 질문을 등록하고 나면 같은 질문이 보이는 마법...

https://www.acmicpc.net/board/view/63126

글 읽기 - 14888번 연산자 끼워넣기 문제 (파이썬) 시간초과 에러가 해결이 안됩니다 ㅠㅠ

이 글에 의하면 eval()에서 time limit이 뜬다고 한다. 그렇다면 없애야지 뭐...

 

eval로 계산하지 않을거면, 사실 인터넷에 돌아다니는 코드대로 하는 수 밖에 없는 것 같다.

n = int(input())
number = list(map(int, input().split()))
plus, minus, multiply, devide = list(map(int, input().split()))

maxnum = -1000000000
minnum = 1000000000

def dfs(num, index, plus, minus, multiply, devide):
    global maxnum, minnum
    if index == (len(number)-1):
        maxnum = max(num, maxnum)
        minnum = min(num, minnum)
        return
    if plus > 0:
        dfs(num + number[index+1], index+1, plus-1, minus, multiply, devide)
    if minus > 0:
        dfs(num - number[index+1], index+1, plus, minus-1, multiply, devide)
    if multiply > 0:
        dfs(num * number[index+1], index+1, plus, minus, multiply-1, devide)
    if devide > 0:
        dfs(int(num / number[index+1]), index+1, plus, minus, multiply, devide-1)

def main():
    num = number[0]
    dfs(num, 0, plus, minus, multiply, devide)
    print(maxnum)
    print(minnum)

main()

이 코드대로라면 통과는 된다. 흠. 그러나 온전히 내가 푼 게 아니라 찝찝하구만.