[Brute Force] 백준 2529번 : 부등호 - 파이썬 Python

 

생각하기

최대와 최소를 구하면 되므로 최대와 최소를 나누어서 brute force 하기로 생각한다

최대인 경우 앞자리가 제일 높은 수 (9) 부터 내려오면서 모든 경우를 대입한다

최소인 경우 앞자리가 제일 낮은 수 (0) 부터 올라가면서 모든 경우를 대입힌다.

 

recursive한 메소드를 사용하여 각각의 경우에 대해 검증한다. 

최대 구하는 경우

• flag가 False 인 경우 return
• step이 k+2인 경우 flag를 False로 세팅하고 출력 그리고 return
• 최대 수부터 아래로 부등호에 맞게 숫자를 넣어가면서 recursion

 

최소 구하는 경우

• flag가 False 인 경우 return
• step이 k+2인 경우 flag를 False로 세팅하고 출력 그리고 return
• 최소 수부터 위로 부등호에 맞게 숫자를 넣어가면서 recursion

import sys
from collections import deque
input = sys.stdin.readline

K = int(input())

op = list(map(str, input().split()))

mem = [False] * 10
ans = []
flag = True

def max_search(step, num):
    global flag, ans, mem

    if flag == False:
        return
    
    if step == K:
        flag = False
        print(str(''.join(ans)))
        return

    if op[step] == '>':
        for new_num in range(num-1, -1, -1):
            if mem[new_num] == False:
                ans.append(str(new_num))

                mem[new_num] = True
                max_search(step+1, new_num)
                mem[new_num] = False
                ans.pop()
    else:
        for new_num in range(9, num, -1):
            if mem[new_num] == False:
                ans.append(str(new_num))
  
                mem[new_num] = True
                max_search(step+1, new_num)
                mem[new_num] = False
                ans.pop()

        
def min_search(step, num):
    global flag, ans, mem

    if flag == False:
        return
    
    if step == K:
        flag = False
        print(str(''.join(ans)))
        return

    if op[step] == '>':
        for new_num in range(0, num):
            if mem[new_num] == False:
                ans.append(str(new_num))
                mem[new_num] = True
                min_search(step+1, new_num)
                mem[new_num] = False
                ans.pop()

    else:
        for new_num in range(num+1, 10):
            if mem[new_num] == False:
                ans.append(str(new_num))
                mem[new_num] = True
                min_search(step+1, new_num)
                mem[new_num] = False
                ans.pop()


for i in range(9, -1, -1):
    if flag == True:
        ans.append(str(i))
        mem[i] = True
        max_search(0, i)
        ans.pop()
        mem[i] = False


mem = [False] * 10
ans = []
flag = True
for i in range(0, 10):
    if flag == True:
        ans.append(str(i))
        mem[i] = True
        min_search(0, i)
        ans.pop()
        mem[i] = False

 

 

순열을 이용해서 문제를 해결할 수 있다

순열 : 중복되지 않은 수로 순서를 섞어서 만들 수 있는 수열

 

선택한 수가 모두 다르기 때문에 순열을 사용할 수 있다.

일반적인 순열은 N개가 있고, 순서를 고려해서 정답을 구한다

하지만 이 문제는 K+1개가 있고 0~9 중에서 K+1개를 고르고 순서를 고려해야 한다!

 

그러나 이 문제에서 아무런 K+1개의 수만 뽑아서 부등호를 고려하여 배치가 가능하다

 

문제의 조건은 조합된 가장 큰수와 작은수를 구하는 것이기 때문에 

• 가장 작은 수 : 0부터 K+1개의 숫자의 조합으로 이루어진 수열 중 가장 작은 수
• 가장 큰 수 : 어떤 수부터 9까지의 K+1개의 수를 조합한 수열 중 가장 큰 수 

각각의 경우를 만족하는 모든 수열을 만들어보고 탐색한다

• 가장 작은 수 탐색 : 가장 작은 수부터 큰수 방향으로 하나씩 보면서 부등호 조건 만족하는지 검사
• 가장 큰 수 탐색 : 가장 큰 수부터 작은수 방향으로 하나씩 보면서 부등호 조건 만족하는지 검사

 

시간 복잡도

(k+1)! x O(k) -> k+1 <=10 이므로 1억보다 작으니 구할 수 있다