같은 것이 있는 순열(복수순열) 배우기 - 숫자 만들기 -

1. 문제

 

4008. [모의 SW역량테스트] 숫자 만들기

 

SW Expert Academy

SW Expert Academy

 

주어진 숫자들 사이에 연산자를 집어넣어 왼쪽부터 오른쪽으로 우선순위를 무시하고 순서대로 계산을 할때,

 

가능한 계산결과의 최댓값과 최솟값의 차이를 구하시오

 

 

2. 같은 것이 있는 순열

 

배열의 원소들 중에 같은 것이 포함된 복수순열은 어떻게 구현할 수 있을까?

 

일반 순열을 구현할때는 배열의 j번째 원소를 사용했는지 여부를 나타내는 used를 사용해서 구현을 했는데

 

def permutation(i,n,r):
    
    if i == r:
        
        print(p)
    
    else:
        
        for j in range(n):
            
            if used[j] == 0:
                
                used[j] = 1
                
                p[i] = a[j]
                
                permutation(i+1,n,r)
                
                used[j] = 0

n = 4

a = [1,2,3,4]

used = [0] * n
p = [0] * n

permutation(0,4,4)
"""
[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 2, 3]
[1, 4, 3, 2]
[2, 1, 3, 4]
[2, 1, 4, 3]
[2, 3, 1, 4]
[2, 3, 4, 1]
[2, 4, 1, 3]
[2, 4, 3, 1]
[3, 1, 2, 4]
[3, 1, 4, 2]
[3, 2, 1, 4]
[3, 2, 4, 1]
[3, 4, 1, 2]
[3, 4, 2, 1]
[4, 1, 2, 3]
[4, 1, 3, 2]
[4, 2, 1, 3]
[4, 2, 3, 1]
[4, 3, 1, 2]
[4, 3, 2, 1]
"""

 

 

같은 것이 있는 순열은 "중복을 허용하지만 배열의 원소의 개수만큼 사용가능"이라는 의미와 같다

 

그래서 used 배열 대신에 count배열을 사용해서, 각 원소의 count를 구한 다음에,

 

각 원소를 순열에 집어넣을때, count를 1 감소시키면서, count=0이면 더 이상 순열에 넣지 않는다

 

def permutation_with_same(i,n,r,cnt):
    
    if i == r: ##r개를 뽑으면 순열 완성
        
        print(p) ##완성된 순열 p로 할 행동
    
    else:
        
        for j in range(1,n+1): ##배열에는 1부터 n까지 원소가 존재함(적절하게 응용하기)
            
            if cnt[j] != 0: ##원소 j의 개수가 0개가 아니라면..
                
                p[i] = j #i번째에는 j를 넣고..

                cnt[j] -= 1 ##j 원소를 1개 사용함

                permutation_with_same(i+1,n,r,cnt) ##다음 i+1번째 원소를 선택하러

                cnt[j] += 1 ##재귀 끝나고 원상복구
    
n = 4

a = [1,1,2,3]

##counting 배열 완성
cnt = [0]*(n+1)

for i in range(n):
    
    cnt[a[i]] += 1

p = [0]*n

permutation_with_same(0,n,n,cnt)

"""
[1, 1, 2, 3]
[1, 1, 3, 2]
[1, 2, 1, 3]
[1, 2, 3, 1]
[1, 3, 1, 2]
[1, 3, 2, 1]
[2, 1, 1, 3]
[2, 1, 3, 1]
[2, 3, 1, 1]
[3, 1, 1, 2]
[3, 1, 2, 1]
[3, 2, 1, 1]
"""

 

한번 조금만 따라가볼까??

 

p = [0,0,0,0]인 상태에서, 1이 2개, 2가 1개 3이 1개있을때 p에 채워넣어야하는데..

 

먼저 i=0에 채워넣을건데 for j in range(1,5): 에서 j=1이 2개 있으므로...

 

p = [1,0,0,0]인 상태로 i+1 = 1인 자리 채워넣기. 그리고 1은 1개, 2는 1개, 3은 1개

 

다음 for j in range(1,5): 에서 j=1이 1개 있으므로...

 

p = [1,1,0,0]인 상태이고.. 1은 0개 2는 1개 3은 1개이고 i+1=2인 자리에 넣기

 

다음 for j in range(1,5): 에서 j=1이 0개 있으니 넘어가고 j=2는 1개 있으니까..

 

p = [1,1,2,0]인 상태이고.. 1은 0개 2는 0개 3은 1개이고.. i+1=3인 자리에 넣기

 

for j in range(1,5):에서 j=1,2는 0개 있으니 넘어가고 j=3은 1개 있으니까.. 넣고

 

p = [1,1,2,3]인 상태로.. i=4에서 p를 출력하고

 

재귀 끝났으니까 되돌아가면서..

 

j=3인 cnt 원상복구.. 1은 0개 2는 0개 3은 1개

 

p = [1,1,2,0]인 상태로.. for j in range(1,5):에서 j=3이 끝났으니 j=4가 되는데 j=4는 없으니까 넘어가고..

 

j=2인 cnt 원상복구.. 1은 0개 2는 1개 3은 1개..

 

p = [1,1,0,0]인 상태에서... for j in range(1,5):에서 j=2가 끝났으니까.. j=3이 되는데..

 

그러면 3은 1개 있으니까 집어넣고 p = [1,1,3,0]인 상태로.. 새롭게 i = 3인 상태로 1은 0개, 2는 1개, 3은 0개로 넘어가기..

 

다시 for j in range(1,5):에서  1은 0개, 2는 1개, 3은 0개상태에서 반복문 도는데.. j=2일때 채워넣을 수 있고..

 

p = [1,1,3,2]가 만들어지고.. 출력

 

... 되돌아가면서..

 

p = [1,1,0,0]에서 for j in range(1,5):에서 j=3도 끝나고.. j=4차례인데... j=4가 없으니까 넘어가고

 

p = [1,0,0,0]에서 cnt는 1은 1개, 2는 1개, 3은 1개인 상태로.. for j in range(1,5):에서 j=1이 끝나고.. j=2가 된 상태에서..

 

p=[1,2,0,0]이고.. cnt는 1은 1개, 2는 0개, 3은 1개인 상태로... 계속 반복...

 

 

3. 실전 문제에 적용

 

이제 위 문제에 적용해보자

 

숫자 사이에 +,-,*,/을 넣는 문제다.

 

숫자의 위치는 고정되므로, +,-,*,/의 연산자를 일렬로 배열해서 수식 사이에 넣어보고

 

계산값의 최댓값과 최솟값을 완전 탐색하면 된다

 

 

그런데 +나 -나 *이나 /의 개수는 여러개 일 수 있어서.. 일반적인 순열을 구현하는 식으로 하면

 

중복되는 연산을 너무 많이하게 된다

 

같은 것이 있는 순열을 직접 구현해서 효율적인 탐색을 수행하자

 

 

def dfs(num_list,op_list,i,n,r):
    
    global max_v,min_v ##최댓값과 최솟값의 전역변수 선언
    
    ##r개를 전부 뽑아서 순열을 하나 완성하면...
    if i == r:
        
        ##맨 처음 숫자는 빼놓고
        result = num_list[0]
        
        ##연산자, 다음숫자를 차례대로 한꺼번에 뽑고
        
        for op,num in zip(perm_op,num_list[1:]):
            
            ##0이면 +, 1이면 -, 2이면 *, 3이면 /이니까.. 각각에 맞게 연산 수행
            
            if op == 0:
                
                result += num
            
            elif op == 1:
                
                result -= num
            
            elif op == 2:
                
                result *= num
            
            else:
                
                result = int(result/num)
        
        ##최댓값 or 최솟값 갱신
        if max_v < result:
            
            max_v = result
        
        if min_v > result:
            
            min_v = result
    
    else:
        
        ##가능한 연산자는 0,1,2,3
        for op in range(4):
            
            ##op의 count가 0이 아니라면..
            
            if op_list[op] != 0:
                
                ##순열 i번째 원소에 op를 채워넣고
                perm_op[i] = op

                op_list[op] -= 1 ##counting 1 감소..
                
                ##다음 i+1번째 원소를 채우러 이동

                dfs(num_list,op_list,i+1,n,r)

                op_list[op] += 1 ##재귀가 끝나면.. counting 복구..
               

T = int(input())

for tc in range(1,T+1):
    
    n = int(input())
    
    ##연산자의 counting 배열
    ##0,1,2,3은 각각 +,-,*,/을 나타내고
    ##각각 연산자의 개수

    op_list = list(map(int,input().split())) 
    
    ##주어진 숫자 리스트

    num_list = list(map(int,input().split()))
    
    ##숫자의 범위가 -100000000~100000000이므로.. 최대 최소 초기화
    max_v = -100000000
    min_v = 100000000
    
    ##연산자의 같은 것이 있는 순열을 만들 리스트
    perm_op = [0]*(n-1)
    
    ##같은 것이 있는 순열을 이용한 탐색
    ##연산자 수는 n-1개이므로.. n-1개에서 n-1개를 뽑는 순열
    dfs(num_list,op_list,0,n-1,n-1)

    print('#'+str(tc),max_v-min_v)

 

 

나눗셈에서.. int(result/num)을 수행했는데 

 

result//num을 수행하면.. 음수의 경우 결과가 이상하게 나온다

 

 

 

4. 최적화하기

 

길이 n-1인 순열을 완성하고 나서, 그것을 순회해서 연산을 수행했으니 당연히 비효율적이다

 

조금 응용해서 연산자를 하나 뽑을때마다 바로 연산을 수행하고 모든 숫자를 뽑으면, 최대 최소를 갱신한다

 

def dfs(num_list,op_list,i,n,result):
    
    global max_v,min_v
    
    ##n-1개의 연산자를 뽑으면 최대, 최소를 갱신
    
    if i == n:
        
        if max_v < result:
            
            max_v = result
        
        if min_v > result:
            
            min_v = result
    
    else:
        
        ##연산자 0,1,2,3에서 뽑고..
        
        for op in range(4):
            
            ##연산자가 아직 남아있다면..
            
            if op_list[op] != 0:
                
                ##그 연산자를 사용하고 counting 1 감소
                
                op_list[op] -= 1

                ##연산 수행
                ##연산 결과를 임시 변수 dresult에 저장하고..

                if op == 0:
                    
                    dresult = result + num_list[i]
                
                elif op == 1:
                    
                    dresult = result - num_list[i]

                elif op == 2:
                    
                    dresult = result * num_list[i]
                
                else:
                    
                    dresult = int(result/num_list[i])

                ##dresult를 재귀에 넣어줘야.. result는 다른곳에 쓰일수 있겠지?
                ##i번째를 결정시키면.. 다음 i+1번째를 결정하러
                
                dfs(num_list,op_list,i+1,n,dresult)
                
                ##재귀 하나가 끝나면.. 연산자 사용한거 복구
                op_list[op] += 1
               

T = int(input())

for tc in range(1,T+1):
    
    n = int(input())

    op_list = list(map(int,input().split()))

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

    max_v = -100000000
    min_v = 100000000
    
    ##숫자리스트, 연산자리스트, 첫번째 숫자 하나는 이미 뽑았고..
    dfs(num_list,op_list,1,n,num_list[0])

    print('#'+str(tc),max_v-min_v)