[Python/백준] #14888 - [연산자 끼워넣기] / #2504 -[괄호의 값]

[연산자 끼워넣기]-14888번

14888번: 연산자 끼워넣기

My answer

from itertools import permutations

min,max=1000000000,-1000000000 
n=int(input()) #입력할 숫자의 개수

nums=list(map(int,input().split())) #계산할 숫자들
tmp=list(map(int,input().split())) #연산자들의 개수

op='+'*tmp[0]+'-'*tmp[1]+'*'*tmp[2]+'/'*tmp[3] 
op=[i for i in op] #연산자 리스트
allop=list(permutations(op, sum(tmp))) #연산자 순열

for i in allop: #모든조합의 수 반복
    sum=nums[0]
    for j in range(1,len(nums)): #각각의 계산식 
        if(i[j-1]=='+'):
            sum+=nums[j]
        elif(i[j-1]=='-'):
            sum-=nums[j]
        elif(i[j-1]=='*'):
            sum*=nums[j]
        else:
            if(sum<0):
                sum=-((-sum)//nums[j])
            else:
                sum//=nums[j]
    if(sum>max):
        max=sum
    if(sum<min):
        min=sum
print(max)
print(min)

Another answer

from itertools import permutations
N=int(input())
A=list(map(int, input().split()))
a,s,m,d=map(int, input().split())
l=[]
for p in set(permutations('+'*a+'-'*s+'*'*m+'/'*d)):
    r=A[0]
    for i in range(1,N):
        r={'+':r+A[i],'-':r-A[i],'*':r*A[i],'/':int(r/A[i])}[p[i-1]]
    l.append(r)
print(max(l), min(l))
-----------------------------------------------------------------------
M=-10**9
m=10**9
N=int(input())
num=list(map(int,input().split()))
a,b,c,d=map(int,input().split())
def inst(n,i,d1,d2,d3,d4):
	global M,m
	if i==N:M=max(M,n);m=min(m,n);return 
	else:
		if d1:inst(n+num[i],i+1,d1-1,d2,d3,d4)
		if d2:inst(n-num[i],i+1,d1,d2-1,d3,d4)
		if d3:inst(n*num[i],i+1,d1,d2,d3-1,d4)
		if d4:inst(int(n/num[i]),i+1,d1,d2,d3,d4-1)
inst(num[0],1,a,b,c,d)
print(M)
print(m)

우선 내가 푼 방법과 밑에것중 첫번째랑 동일한 방법인데 내껀 시간초과가 난다. 그 이유는 permutations를 통해 구한 순열의 갯수가 너무 많기 때문인데, 왜 아래 코드는 안나냐면 set()집합을 통해서 중복된 순열을 모두 없앴기 때문이다.. 똑똑하다.. 그 이외에는 똑같다. 마지막 코드는 재귀를 통해서 짠건데 재귀는 어떻게 짜야할 지 모르겠다 뭔가 전부 알고난후에 바꾸는건 가능해도 처음부터 재귀로는 못짤 것 같다..내머리가 이해가 안간다. 

[괄호의 값]-2504번

2504번: 괄호의 값

My answer

tmp,tmp2,sum=[],[],0
a=input()
a=[i for i in a]
# 완전한 괄호인지 확인하는 코드
for i in a:
    if(tmp==[]):
        tmp.append(i)
        continue
    if(i=='(' or i=='['):
        tmp.append(i)
    elif(i==')'):
        if(tmp[-1]=='('):
            tmp=tmp[:-1]
        else:
            tmp.append(i)
    else:
        if(tmp[-1]=='['):
            tmp=tmp[:-1]
        else:
            tmp.append(i)
if(len(tmp)!=0):
    print(0)
else:
    for i in a:
        if(tmp2==[]):
            tmp2.append(i)
            continue
        if(i=='(' or i=='['):
            tmp2.append(i)
        elif(i==')'):
            if(tmp2[-1]=='('):
                tmp2=tmp2[:-1]
                tmp2.append('2')
            else:
                tmp2.append(i)
        else:
            if(tmp2[-1]=='['):
                tmp2=tmp2[:-1]
                tmp2.append('3')
            else:
                tmp2.append(i)
    while(len(tmp2)!=1):
        for i in range(len(tmp2)-1):
            if(tmp2[i].isdigit()):
                if(tmp2[i-1]=='(' and tmp2[i+1]==')'):
                    tmp2[i]=str(int(tmp2[i])*2)
                    tmp2[i-1]='0'
                    tmp2[i+1]='0'
                elif(tmp2[i-1]=='[' and tmp2[i+1]==']'):
                    tmp2[i]=str(int(tmp2[i])*3)
                    tmp2[i-1]='0'
                    tmp2[i+1]='0'
                elif(tmp2[i+1].isdigit()):
                    tmp2[i]=str(int(tmp2[i])+int(tmp2[i+1]))
                    tmp2[i+1]='0'
        while(tmp2.count('0')!=0):
            tmp2.remove('0') 
    print(int(tmp2[0]))

Another answer

def f(p):
    if len(p) == 0 : return 1
    dic = {'(':')', '[':']'}
    val, sub, stk = 0, '', []

    for i in p:
        sub += i
        if len(stk) > 0 and dic.get(stk[-1], '') == i : 
            stk.pop()
        else : 
            stk.append(i)
        if len(stk) == 0 : 
            val += f(sub[1:-1]) * (2 if sub[0] == '(' else 3)
            sub = ''
    if len(stk) > 0 : 
        return 0
    return val
print(f(input()))

우선 나는 그냥 문제를 풀기위해 개멍청하게 풀은것 같다..우선 완전한 괄호인지 확인을 하고, 또 계산을 엄청 복잡하게 이중반복문을 통해서 구했다...엄청 힘들게 풀었는데 아래 코드는 우선 내가 if,else 뻘짓한걸 딕셔너리와 pop으로 엄청 간단하게 구현했고, 완전괄호와 계산하는걸 분리시키지 않고 한번에 재귀를 통하여 구하였다. 우선 재귀는 가장 바깥쪽부터 풀어가면서 계산한 것 같다.