백준 14888번 - 연산자 끼워넣기(삼성 SW 역량 테스트 기출 1)

 

처음에 문제를 보고 숫자도 문자열로 받은 뒤 입력 개수만큼 문자'+','-','x','//'를 받아서 하나씩 빼주면서 정수로 변환해서 계산을 해야겠다고 생각했다. 조금 복잡한 것 같지만 생각보다 그렇게 복잡하지는 않았다. 하지만 문제는 중복되는 순열도 모두 계산을 해야 하는 것이었다. 6개의 숫자를 받는다고 할 때 연산자가 만약 + + + - - 라고 할 때 내 계산을 그저 5! 의 경우를 모두 계산했다. 중복 문제를 해결하지 못했다. 그래도 예제의 출력 값은 제대로 나와서 백준에 제출했을 때 적어도 시간 초과라도 뜨겠구나 싶었지만, 틀렸다고 나왔다. 어느 부분에서 출력의 오류가 있었는지는 잘 모르겠다.

##함수 선언 부분
def calculator(Numbers):
    global min, max
    if len(Numbers) == N*2 - 1: #연산자가 모두 들어갔으면
        ans = calculate(Numbers)
        if min > ans:
            min = ans
        if max < ans:
            max = ans


    else:
        for i in range(len(cal)): #연산자 개수만큼
            Numbers.append(cal[i]) #연산자를 뒤에 붙여준다.
            cal.pop(i)
            calculator(Numbers)
            tmp = Numbers.pop()
            cal.insert(i, tmp)

def calculate(_numbers):
    sum = int(_numbers[0])
    for i in range(N-1):
        if _numbers[i + N] == '+':
            sum = sum + int(_numbers[i+1])

        elif _numbers[i + N] == '-':
            sum = sum - int(_numbers[i+1])

        elif _numbers[i + N] == 'x':
            sum = sum * int(_numbers[i+1])
        else:
            if sum < 0:
                sum *= -1
                sum = sum // int(_numbers[i+1])
                sum *= -1
            else:
                sum = sum // int(_numbers[i+1])

    return sum

##변수 선언 부분
numbers = []
cal = []
min = 1000000000
max = -1000000000
cnt = 0
##메인 함수 부분
if __name__ == "__main__":
    N = int(input())
    numbers = [x for x in input().split()] #숫자를 문자열로 입력
    a, b, c, d = map(int, input().split()) #+,-,x,// 개수 입력
    for i in range(a): #입력 횟수만큼 배열에 넣어준다
        cal.append('+')
    for i in range(b):
        cal.append('-')
    for i in range(c):
        cal.append('x')
    for i in range(d):
        cal.append('//')
    calculator(numbers)
    print(max)
    print(min)

 

 

같은 것이 있는 순열인 경우에 중복을 어떻게 하면 없애는 지 생각해봤는데, 각 연산자의 개수를 줄여가면서 없으면 넘어가 주는 식으로 하면 각 +, -, x, //의 개수에 상관없이 중복이 안 되겠구나 싶었다. 그래서 입력 값도 개수로 주어진 것 같다. 계산을 해줄 때도 한 번에 해주는 것이 아니라 재귀 함수를 호출할 때마다 한 번씩 계산한 값을 다시 보내주면서 코드를 짰다. 역시 cnt를 해보니 5개의 경우엔 5!/2! 인 60이 나왔다. 

##함수 선언 부분
def calculator(index, sum):
    global min, max
    if index == N - 1: #연산자가 모두 들어갔으면
        if min > sum:
            min = sum
        if max < sum:
            max = sum

    else:
        for i in range(4): #연산자 4개 탐색
            if cal[i] == 0: #특정 연산자를 다 썼으면
                continue #그대로 진행
            cal[i] -= 1 #연산자 하나를 빼서
            temp = calculate(sum,numbers[index+1],i) #계산을 해주고
            calculator(index+1,temp) #계산한 값을 다시 재귀
            cal[i] += 1 #백트래킹

def calculate(sum, plus, oper): #연산자마다 계산
    if oper == 0:
        return sum + plus
    elif oper == 1:
        return sum - plus
    elif oper == 2:
        return sum * plus
    else:
        if sum < 0:
            sum = -sum // plus
            return -sum
        else:
            return sum // plus

##변수 선언 부분
numbers = []
cal = []
min = 1000000000
max = -1000000000
cnt = 0
##메인 함수 부분
if __name__ == "__main__":
    N = int(input())
    numbers = [int(x) for x in input().split()] #숫자 입력
    cal = [int(x) for x in input().split()] #+,-,x,// 개수 입력
    calculator(0,numbers[0])
    print(max)
    print(min)

 

어렵지 않은 문제였지만 처음에 너무 어렵게 풀었던 것 같다. 또한 중복을 해결하지 않고 무작정 구현하다 보니 오답이 나왔다. 같은 것이 있는 순열을 구현할 때는 개수를 세서 하나씩 줄여가며 구현해야한다는 것을 배웠다. 충분히 쉽게 풀 수 있었는데 시간이 좀 걸린 것 같아서 아쉬웠던 문제다.