[파이썬] 백준 연산자 끼워넣기

14888번: 연산자 끼워넣기

---

나의 풀이

• +, -,*, / 연산자 각 원소의 개수에 맞춰서 인덱스 리스트를 만들어서 저장했다.
• 이후 인덱스 리스트로 순열을 만들어서 완전 탐색을 진행해서 풀었다.
• 순열을 직접 구현하고 사용해보려고 이런 방식으로 풀었는데, itertools의 permutations 함수를 사용하면 통과가 되지만 구현한 수열 함수로는 시간 초과가 발생한다.

def get_perm(arr, n):
    perm_list = []
    # 종료 조건
    if n == 0:
        return [[]]
    # 현재 arr의 담긴 수를 확인
    for i in range(len(arr)):
        # 선택된 수
        num = arr[i]
        # 나머지 수로 구성된 배열
        arr_left = arr[:i] + arr[i+1:]
        for perm in get_perm(arr_left, n - 1):
            perm_list.append([num] + perm)
    return perm_list
# 수의 개수
N = int(input())
# 입력 수
num_list = list(map(int, input().split()))
op_cnt = list(map(int, input().split()))
op_list = ["+", "-", "*", "/"]
# 연산자 인덱스 저장
op_idx = []
for i in range(4):
    # 개수 만큼 반복
    for j in range(op_cnt[i]):
        op_idx.append(op_list[i])
# 결과 저장
max_val = -1e9
min_val = 1e9

for perm in get_perm(op_idx, len(op_idx)):
    total = num_list[0]
    for i, op in enumerate(perm):
        if op == "+":
            total += num_list[i + 1]
        elif op == "-":
            total -= num_list[i + 1]
        elif op == "*":
            total *= num_list[i + 1]
        else:
            # 음수 경우 처리
            if total < 0:
                total = - (abs(total) // num_list[i + 1])
            else:
                total //= num_list[i + 1]                        
    if total > max_val:
        max_val = total
    if total < min_val:
        min_val = total
    
print(max_val, min_val, sep = "\n")

다른 풀이

• DFS와 백트래킹을 활용해서 풀 수도 있다.
• 풀이는 교재를 참고했다.

N = int(input())
num_list = list(map(int, input().split()))
op_cnt = list(map(int, input().split()))

# 최댓값, 최솟값 초기화
min_val = 1e9
max_val = -1e9

def dfs(i, now):
    # 값 변경위해서 global 선언
    global min_val, max_val
    if i == N:
        min_val = min(min_val, now)
        max_val = max(max_val, now)
    else:
        # 각 연산자에 대해서 재귀적으로 수행
        # + 연산자
        if op_cnt[0] > 0:
            op_cnt[0] -= 1
            dfs(i + 1, now + num_list[i])
            # 다시 되돌리기
            op_cnt[0] += 1
        # - 연산자
        if op_cnt[1] > 0:
            op_cnt[1] -= 1
            dfs(i + 1, now - num_list[i])
            op_cnt[1] += 1
        # * 연산자
        if op_cnt[2] > 0:
            op_cnt[2] -= 1
            dfs(i + 1, now * num_list[i])
            op_cnt[2] += 1
        # / 연산자
        if op_cnt[3] > 0:
            op_cnt[3] -= 1
            dfs(i + 1, int(now / num_list[i]))
            op_cnt[3] += 1

dfs(1, num_list[0])
# 최댓값 - 최솟값 차례대로 출력
print(max_val, min_val, sep = "\n")

---

참고

이것이 취업을 위한 코딩테스트다 with 파이썬