(파이썬) 백준 알고리즘 - 14888번 / permutation()

연산자 끼워넣기

https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

 

수와 연산자들을 입력받은 후 해야할 일을 정리해봤다.

1. 개수로 입력받은 연산자를 사용할 수 있도록 바꿔준다

2. 연산자를 중복없이 배열한다

3. 입력받은 숫자 순서대로 연산한다

문제에서는 연산자 순서(* / 먼저, + - 나중)상관없이 앞에서부터 계산해야 한다고 했다.

N = int(input())
numbers = list(map(int, input().split()))
operators = list(map(int, input().split()))
 
# 연산자 개수대로 operatorSigns에 저장
operatorSigns = []
for index, value in enumerate(operators):
    for _ in range(value):
        operatorSigns.append(index)

operatorSigns를 따로 만들어 세 번째 예제의 경우 [2, 1, 1, 1]로 입력받은 연산자들을 0 두개, 1, 2, 3 한개씩 저장한다.

(operatorSigns == [0, 0, 1, 2, 3])

 

그리고 1부터 N까지의 수를 중복없이 배열했다.(15649번에서 코드 가져옴) 

# 연산자 순열 만들기
s = []
result = []
def dfs():
    if len(s)==N-1:
        result.append(calculate(s))
        return
    
    for i in range(1,N):
        if i not in s:
            s.append(i)
            dfs()
            s.pop()
 
dfs()

사실 [0, 0, 1, 2, 3]과 같이 같은 수가 있는 경우의 순열을 구하고 싶었는데 잘 안됐다. 그렇게 구한 순열을 가지고 calculate()를 실행해서 계산된 값을 구한다.

def calculate(signs):
    num = numbers[0]
    for i in range(N-1):
        index = signs[i] - 1
        if operatorSigns[index] == 0:
            num = num + numbers[i+1]
            continue
        elif operatorSigns[index] == 1:
            num = num - numbers[i+1]
            continue
        elif operatorSigns[index] == 2:
            num = num * numbers[i+1]
            continue
        elif operatorSigns[index] == 3:
            if num < 0:
                num = -num // numbers[i+1]
                num = -num
            else: 
                num = num // numbers[i+1]
            continue
    return num

calculate()에서는 전달받은 1부터 5까지의 수들의 순열을 가지고 계산한다.

만약 전달받은 순열이 s == signs == [3, 1, 4, 5, 2] 라면 operatorSigns == [0, 0, 1, 2, 3]에서 3번째, 1번째, 4번째, 5번째, 2번째 연산자인 - + * / + 순서대로 계산하는 것이다.

이렇게 구한 값을 result에 입력하고, 최대값은 max(result), 최소값은 min(result)로 출력한다.

전체적인 코드는 아래와 같다.

 

(이 코드는 python으로 제출했을 땐 시간초과, PyPy3으로 제출했을 땐 통과했다.)

N = int(input())
numbers = list(map(int, input().split()))
operators = list(map(int, input().split()))
 
# 연산자 개수대로 operatorSigns에 저장
operatorSigns = []
for index, value in enumerate(operators):
    for _ in range(value):
        operatorSigns.append(index)
 
# 계산하기
def calculate(signs):
    num = numbers[0]
    for i in range(N-1):
        index = signs[i] - 1
        if operatorSigns[index] == 0:
            num = num + numbers[i+1]
            continue
        elif operatorSigns[index] == 1:
            num = num - numbers[i+1]
            continue
        elif operatorSigns[index] == 2:
            num = num * numbers[i+1]
            continue
        elif operatorSigns[index] == 3:
            if num < 0:
                num = -num // numbers[i+1]
                num = -num
            else: 
                num = num // numbers[i+1]
            continue
    return num
 
 
# 연산자 순열 만들기
s = []
result = []
def dfs():
    if len(s)==N-1:
        result.append(calculate(s))
        return
    
    for i in range(1,N):
        if i not in s:
            s.append(i)
            dfs()
            s.pop()
 
dfs()
 
print(max(result))
print(min(result))

코드 자체는 틀리지 않았지만 더 빠르게 할 수 있는 방법을 찾다가 다른 사람이 제출한 답변 중 빠른 답변을 보게됐다.

import sys
from itertools import permutations
 
# 수의 개수
N = int(sys.stdin.readline())
# 주어진 수들
nums = list(map(int, sys.stdin.readline().split()))
# 연산자
operator_list = list(map(int, sys.stdin.readline().split()))
operators = []
for i, op in enumerate(operator_list):
    if i == 0:
        operators += ['+'] * op
    elif i == 1:
        operators += ['-'] * op
    elif i == 2:
        operators += ['*'] * op
    else:
        operators += ['//'] * op
 
permuted_operators = list(set(permutations(operators)))
 
vals = []
 
for op in permuted_operators:
    val = nums[0]
    for num, o in zip(nums[1:], op):
        if o == '+':
            val += num
        elif o == '-':
            val -= num
        elif o == '*':
            val *= num
        else:
            if val < 0:
                val = (-1) * (((-1) * val) // num)
            else:
                val //= num
    vals.append(val)
 
print(max(vals))
print(min(vals))

(https://www.acmicpc.net/source/33121281)

나랑 같은 방법으로 만들었는데, 구현하는 방법은 달랐다.

from itertools import permutations
# 연산자
operator_list = list(map(int, sys.stdin.readline().split()))
operators = []
for i, op in enumerate(operator_list):
    if i == 0:
        operators += ['+'] * op
    elif i == 1:
        operators += ['-'] * op
    elif i == 2:
        operators += ['*'] * op
    else:
        operators += ['//'] * op
 
permuted_operators = list(set(permutations(operators)))

일단 입력받은 연산자 개수들을 operators 리스트에 넣는것은 같다(이 코드는 숫자 대신 문자를 넣음).

그런데 연산자의 순열을 구할 때 아래와 같은 코드를 사용했다.

from itertools import permutations

permuted_operators = list(set(permutations(operators)))

permutations라는 외장함수를 사용해 순열을 구한 것이다.

console에 operators와 permuted_operators 를 확인해보면 아래와 같다.

(예제 입력 3의 경우)

+가 2개 있는 것을 고려해서 순열을 만들어준다.

이 부분에서 속도의 차이가 만들어진다. 내가 작성한 코드는 중복된 연산자를 고려하지 않기 때문에 다섯 가지 모두 다른 연산자로 취급해 많은 순열을 만들기 때문이다.

같은 연산자가 2개만 있어도 위의 permutation()을 사용한 경우는 60개의 순열을, 아래 사용하지 않았을 때는 120개의 순열을 만든다.(사용하지 않은 경우에는 calculate()가 얼마나 호출되는지 counter를 사용해 구했다)

 

다른 부분은 방법은 같다. 하지만 시간 차이가 크다

파이썬의 새로운 외장함수를 알게되었으니 문제를 해결할 때 잘 사용할 수 있도록 신경써봐야겠다.

 

 

 

참고한 사이트

https://www.acmicpc.net/source/33129127

로그인

https://hckcksrl.medium.com/python-permutation-combination-a7bf9e5d6ab3

Python permutation , combination