완전탐색 순열과 조합 연습장2 -앞자리에 0이 못오게 하기-

1. 문제1

 

2529번: 부등호 (acmicpc.net)

2529번: 부등호

 

k개의 부등호가 주어질때, 0~9까지에서 k+1개의 수를 1번씩만 선택해 주어진 부등호 순서를 모두 만족시킬때

 

이들을 하나로 합친 수의 최댓값과 최솟값을 구하는 문제

 

 

2. 풀이

 

10개중에 k+1개를 선택하는 순열을 검사해서 부등호를 모두 만족시키는지 검사해보고 조건을 만족시키면

 

최댓값과 최솟값을 갱신한다

 

어차피 각 수는 1개씩만 사용가능하니까 숫자를 문자열로 다뤄도 될 것이다

 

숫자문자열끼리 비교하면 맨 앞자리부터 크면 큰건데 1개씩만 사용가능하니까 int로 안바꿔도 상관 없는 부분

 

최솟값을 초기화할때는 어렵게 생각하지 말고 9를 k+1개만큼 나열하면 될것

 

used배열 이용해서 10개중에 k+1개 뽑는 순열을 만들고..

 

순열 하나를 완성시키면

 

p는 k+1개가 있고 inequal_list에는 k개가 있는데

 

num_value에 먼저 p[0]를 넣고 p[1:]와 inequal_list를 동시에 순회하는 zip을 이용

 

num_value의 마지막 원소인 num_value[-1]과 p[1:]의 원소를 부등호로 비교해보면 될 것

 

조건에 맞으면 num_value를 계속 이어주고, 아니면 그냥 바로 break시키자

 

from sys import stdin

def permutation(i,n,r,inequal_list):
    
    global max_value,min_value
    
    if i == r:
        
        num_value = p[0] #첫 수를 먼저 이어 붙이고
        find = True #조건을 만족시키는 수를 찾았는지 flag
        
        #inequal_list와 p를 동시에 순회
        for inequal,num in zip(inequal_list,p[1:]):
            
            if inequal == '>':
                 
                 #num_value의 마지막 원소와 p의 원소를 비교
                if num_value[-1] > num:
                    
                    num_value += num
                
                else:
                    #조건에 안맞으면 바로 break시킴
                    find = False
                    break
            
            else:
                
                if num_value[-1] < num:
                    
                    num_value += num
                
                else:
                    find = False
                    break
        
        #찾았으면 최댓값, 최솟값을 갱신
        if find == True:
            
            if num_value > max_value:
                
                max_value = num_value
            
            if num_value < min_value:
                
                min_value = num_value

    else:
        
        for j in range(n):
            
            if used[j] == 0:
                
                used[j] = 1

                p[i] = num_list[j]

                permutation(i+1,n,r,inequal_list)

                used[j] = 0

k = int(stdin.readline())

#모든 수는 str()로 받자
num_list = [str(i) for i in range(10)]

inequal_list = stdin.readline().rstrip().split()

p = [0]*(k+1)

used = [0]*10

#max_value와 min_value 초기화
max_value = str(0)
min_value ='9'*(k+1)

permutation(0,10,k+1,inequal_list)

print(max_value)
print(min_value)

 

 

3. 문제2

 

16943번: 숫자 재배치 (acmicpc.net)

16943번: 숫자 재배치

 

A의 순열중에서 B보다 작으면서 가장 큰 값을 구해본다면..?

 

단 맨 앞자리는 0이 올 수 없다

 

 

4. 풀이

 

맨 앞자리에 0이 올수 없다는 것만으로 귀찮아지는 문제

 

0이 못오게 어떻게 순열을 구현할 수 있었을까

 

두 수 a,b를 받고, a에 0이 존재하는지 아닌지를 먼저 검사했음

 

a,b = stdin.readline().rstrip().split()

b = int(b)

n = len(a)

a = list(a)

cnt = [0]*10

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

 

만약에 0이 존재하는 경우라면? cnt[0]가 1이상이라면?

 

0이 아닌 모든 경우를 순열의 앞자리 p[0]에 배치하고 1번부터 n-1번까지 순열을 채워넣었다

 

max_ans = 0

if cnt[0] >= 1:
    
    for i in range(n):
        
        if a[i] != '0':
        
            p = [0]*n
            used = [0]*n

            p[0] = a[i]
            used[i] = 1

            permutation(1,n)

 

 

0이 존재하지 않는다면.. 일반적인 순열을 그냥 구해보면 될 것이다

 

 

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

    permutation(0,n)

 

그러면 순열을 만드는 함수는 쉽게 할 수 있지

 

순열 p를 모두 채워넣으면 숫자로 바꾼 다음에 실제 b보다 작은지 검사하고

 

작다면 최댓값을 갱신하는 방식으로

 

from sys import stdin

def permutation(i,n):

    global max_ans
    
    #n자리 순열을 모두 구성하면
    if i == n:
        
        #정수로 바꿔서 b와 크기 비교
        if int(''.join(p)) < b:
            
            ans = int(''.join(p))
            
            #b보다 작다면, 최댓값인지 검사하고 갱신함
            if max_ans < ans:
                
                max_ans = ans

    else:
        
        for j in range(n):

            if used[j] == 0:
      
                p[i] = a[j]

                used[j] = 1

                permutation(i+1,n)

                used[j] = 0


a,b = stdin.readline().rstrip().split()

b = int(b)

n = len(a)

a = list(a)

#a를 구성하는 원소의 개수를 센다
cnt = [0]*10

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

max_ans = 0

#a의 자리수에 0이 존재한다면..
if cnt[0] >= 1:
    
    for i in range(n):
        
        #0이 아닌 모든 경우에 대하여,
        if a[i] != '0':
        
            p = [0]*n
            used = [0]*n
            
      #맨 앞자리를 0이 아닌 수로 채워넣고
            p[0] = a[i]
            used[i] = 1
      #1번부터 n-1번까지 순열을 채워넣는다
            permutation(1,n)

#0이 존재하지 않는다면.. 그냥 순열을 구한다
else:
    p = [0]*n
    used = [0]*n

    permutation(0,n)

#최댓값이 갱신되지 않았다면, 찾을 수 없다는 뜻
if max_ans == 0:
    
    print(-1)

else:

    print(max_ans)

 

 

5. 되돌아보기

 

완전탐색 계속 연습해서 몸이 기억하게 만들어버리자

 

0이 앞자리에 못오게 할려면?

 

0을 제외한 나머지 수를 하나씩 앞자리에 채워본다음에 1부터 n-1번까지 순열을 채워넣은 모든 경우를 검사해보면 그만