[백준] #2529 부등호 (Python)

부등호

문제

• 입력 : 부등호 문자의 개수를 나타내는 정수 k( 2 ≤ k ≤ 9)와 k개의 부등호 기호
• 출력 : 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수

부등호의 갯수와 부등호가 주어졌을 때, 그 부등호에 맞게 양 옆으로 들어갈 수 있는 숫자(0~9)가 존재한다.(단, 모든 숫자는 달라야 한다.)
주어진 모든 부등호를 만족하는 숫자들을 찾고, 부등호를 제거하면 정수하나가 나오는데, 그들 중 최대값과 최솟값을 반환해야한다.

입력

2
< >

출력

897
021

용어 정리 - 백트래킹

• 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것
• 답이 될 만한지 판단하고 그렇지 않으면 탐색을 중단
• 주로 문제 풀이에서는 DFS 등으로 모든 경우의 수를 탐색하는 과정에서, 조건문으로 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황일 경우에는 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하도록 구현

풀이 전략

• 재귀 함수를 이용하여 브루트 포스(가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져오는 방식)로 구현
• 재귀 함수를 호출하기 전에 부등호 체크를 하는 방식으로 백트래킹을 하여 시간을 단축

1. 하나의 완성된 정수를 구하기 위해서 입력으로 주어진 길이(N)+1 만큼 재귀 함수를 호출해야 한다. (숫자 개수 = 부등호 개수+1)
   재귀 함수 종료 조건 : 숫자 개수(길이) == N+1
2. 수를 중복하여 사용할 수 없으므로, check 배열을 별도로 만들어서 사용 가능 여부를 확인해야 한다.
3. 재귀 함수를 호출하기 전에, 다음 숫자가 부등식에 맞는지 살펴봐야 한다.
   ex) 주어진 부등호가 < > > 라면, 0 < 3 > 2 > 1은 가능하다.
   하지만 3 < 2 > 1 > 0은 불가능하다. 이런 경우, 3 < 2부터 틀린 부등식이므로, 이 뒤로는 재귀함수를 호출할 필요가 없다.
4. 재귀 함수 호출을 0부터 9까지 순서대로 부르므로, 정답의 최솟값은 처음 호출된 값이며, 최댓값은 마지막에 호출된 값이다.

Solutions

solution	time	info
[solution1.py]	224ms	-

n = int(input()) # 부등호 개수
sign = input().split() #부등호
check = [False]*10 # 0~9
mx, mn = "", ""

# 부등호가 성립하는 지 확인하는 함수
def possible(i,j,k):
    if k == '<':
        return i<j
    if k == '>':
        return i>j
    return True

def solve(cnt, z):
    global mx, mn
    if cnt == n+1:
        if not len(mn): # mn이 비워져 있으면 최솟값에 z 넣기
            mn = z
        else: # mn에 값이 있으면 최댓값에 넣기
            mx = z
        return
    for i in range(10):# 0부터 9까지
        if not check[i]: # check[i]이 false이면(중복 방지)
            if cnt==0 or possible(z[-1], str(i), sign[cnt-1]):
                check[i]=True
                solve(cnt+1, z+str(i)) #재귀함수
                # 만약 0 > ? 일 경우 ?에 올 숫자가 없으므로 solve함수가 끝나고 check[0]이 false가 되고 check[1]부터 다시 시작한다.
                check[i]=False


solve(0, "") #solve 함수 돌리기
print(mx)
print(mn)

Reference

https://rebas.kr/755