삼성 SW역량테스트 기출 / 2017 하반기 오후 2번 문제 연산자 배치하기 - DFS / Python 파이썬

 

*문제 출처는 삼성전자, 코드트리에 있습니다.

 

삼멘 2일차

문제 제목: 연산자 배치하기

문제 사이트: https://www.codetree.ai/training-field/frequent-problems/problems/arrange-operator/description?page=1&pageSize=20&tier=1%2C10

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

---

나의 풀이 (처음 풀이 - 순열 이용)

import sys
input = sys.stdin.readline

n = int(input())
nums = list(map(int,input().split()))
cal_cnt = list(map(int,input().split())) # 연산자를 사용할 수 있는 횟수

cal = ['+','-','*'] # 사용가능한 연산자 개수의 합 n-1
cal_list = []

for i in range(3):
    for _ in range(cal_cnt[i]):
        cal_list.append(cal[i])
# print(cal_list)

visited = [False for _ in range(len(cal_list))]
min_ = 1e9
max_ = 0
remain_num = nums[1:].copy()
def DFS(idx,arr,visited_): #permutation
    global min_ ,max_
    if len(arr) == idx:
        result = str(nums[0])
        for i in range(n-1):
            result += arr[i]
            result += str(remain_num[i])
        # print(result)
        min_ = min(min_,eval(result))
        max_ = max(max_,eval(result))
        return
    for i in range(len(cal_list)):
        if visited_[i] == False:
            visited_[i] = True
            DFS(idx,arr + [cal_list[i]],visited_)
            visited_[i] = False
DFS(n-1,[],visited)
if min_ < -1e9:
    min_ = -1e9
if max_ > 1e9:
    max_ = 1e9
print(int(min_),int(max_))

 

흑흑 시간초과

 

너무 가능한 모든 조합을 만들고, 연산자가 10개 이상이면 시간초과가 돼서 테스트 케이스를 통과하지 못했음

 

다른 풀이

[코드트리] 연산자 배치하기

해당 게시글 내용이 너무 깔끔해서 가져왔다.

 

(입력 및 선언)

• n개의 정수를 입력받고, num에 리스트로 저장한다.
• 사용 가능한 연산자의 개수를 plus, sub, multi 변수에 저장한다.
• MIN, MAX를 최솟값과 최댓값으로 초기화한다.
• dfs 함수를 호출한다.
  • 이때 깊이는 1, 최종값은 num 배열의 첫 번째 원소, 연산자의 개수를 인자로 전달한다.

(식 계산하기)

• 만약 깊이가 n까지 도달했다면, 최솟값과 최댓값을 total과 MIN, MAX 값과 비교해서 더 작고/큰 값을 저장한다.
• 만약 plus에 값이 있으면 재귀 호출을 한다.
  • 이때 깊이는 1 더해서 들어가고, total 값에 num[depth] 값을 더하고, plus 개수는 1 감소시켜 호출한다.
• 만약 sub에 값이 있으면 재귀 호출한다.
  • 이때 깊이는 1 증가하고, total - num[depth], sub를 1 감소시킨다.
• multi에 값이 있으면 재귀 호출한다.
  • 이때 깊이는 1 증가하고, total * num[depth], multi를 1 감소시킨다.

(최종 출력)

MIN, MAX 값을 출력한다.

 

def dfs(depth, total, plus, sub, multi):
    global MIN, MAX
    if depth == n:
        MIN = min(MIN, total)
        MAX = max(MAX, total)
    
    if plus:
        dfs(depth + 1, total + num[depth], plus - 1, sub, multi)

    if sub:
        dfs(depth + 1, total - num[depth], plus, sub - 1, multi)
    
    if multi:
        dfs(depth + 1, total * num[depth], plus, sub, multi - 1)


n = int(input())

num = list(map(int, input().split()))
plus, sub, multi = map(int, input().split())

MIN, MAX = float("INF"), -float("INF")
dfs(1, num[0], plus, sub, multi)
print(MIN, MAX)

 

코드 완전 잘짜셨음.. 흑흑

 

조합만 구현하다가 이 코드 보니 살짝 뇌정지가 왔지만

이렇게 간결하게 짜는 법도 연습해야겠다

특히, eval 로 짜는 코드는 안좋다고 들었어서 이분처럼 depth랑 연산자로 가지를 잘뻗는 재귀함수를 만들어야겠음

 

해당 코드로 안보고 짜서 제출함

depth 를 시작할때부터 1로 두는거 주의

import sys
input = sys.stdin.readline

n = int(input())
nums = list(map(int,input().split()))
cal_cnt = list(map(int,input().split())) # 연산자를 사용할 수 있는 횟수
min_ = 1e9
max_ = -1e9
def DFS(depth, total, plus, sub, multi):
    global min_,max_
    if depth == n:
        min_ = min(min_,total)
        max_ = max(max_,total)
        return
    
    if plus:
        DFS(depth + 1, total + nums[depth],plus -1, sub, multi)
    if sub:
        DFS(depth + 1, total - nums[depth],plus, sub-1, multi)
    if multi:
        DFS(depth + 1, total * nums[depth],plus, sub, multi-1)

DFS(1,nums[0],cal_cnt[0],cal_cnt[1],cal_cnt[2])
    
if min_ < -1e9:
    min_ = -1e9
if max_ > 1e9:
    max_ = 1e9
print(int(min_),int(max_))

---

※ 알아야 할 것

- DFS 할때 복잡하게 만들지말고, 가지를 뻗는쪽으로 구현하기