[Python][백준] 2529. 부등호 / 브루트포스,백트래킹 (S1)

링크🔗

https://www.acmicpc.net/problem/2529

---

🗒️파이썬 코드 풀이

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

K = int(input())
lst = list(input().strip())
lst = list(filter(lambda x : x != " ", lst))
rs_lst = []
visited = [0] * 10

def get_num(a,b,sign):
    if sign == "<":
        if a < b : return True
    else:
        if a > b : return True
    return False

def dfs(n,result):
    if n == K+1 :
        rs_lst.append(result)
        return 
    
    for i in range(10):
        if visited[i] == 0 :
            if n == 0 or get_num(result[n-1],str(i),lst[n-1]):
                visited[i] = 1
                dfs(n+1,result+str(i))
                visited[i] = 0

dfs(0,"")
rs_lst = sorted(rs_lst)
print(rs_lst[-1])
print(rs_lst[0])

 

1. 문제를 읽고 dfs로 풀어야 되겠다는 생각한다.

0~9를 모든 자리에 넣어보는 것인데, 백트래킹으로 어느정도 가지치기를 해준다.

- 방문 여부를 확인해서, 한 숫자가 여러번 쓰이는 것 방지
- 부등호의 조건에 맞는 것만 dfs 실행 

 

2. K와 lst를 입력 받고, lst에서 공백을 제거해준다. 

 

3. 백트래킹하여 나온 result값을 넣기 위한 rs_lst, 

방문 체크를 하기위한 visited 리스트를 각각 만들어준다.

 

4. 입력으로 주어진 "<" 는 문자일 뿐 실제 부등호가 아니므로, 

get_num을 통해 해당 문자로도 부등호 판단이 가능하도록 한다.

 

5. dfs의 매개 변수로 dfs의 깊이를 나타내는 n과,

조건이 충족함에따라 계속 더해지는 문자열 result를 받는다.

 

6. 백트래킹에서 깊이 끝에 도달 할 때의 탈출 조건을 만들어주고, 

rs_lst 리스트에 result 결과값을 넣어준다.

 

7. 0~10까지의 수를 반복문으로 확인한다.

조건은 (1)방문하지 않았 때, (2) n = 0, (3) get_num 함수에 True값을 리턴

n=0인 경우는 아직 첫번째 정수 자리여서, get_num 함수를 쓰지 못하여 필요한 조건이다.

get_num 함수의 매개변수로는 (이전 정수, 현재 정수, 부등호)이다. 

🚨 현재 위치 기준으로 이전꺼와 현재의 정수값만 비교하면 된다. 
만일 뒤에 정수들이 부등호에 맞지 않는다면, rs_lst 리스트에 저장이 안된다.

 

8. 해당 조건들을 다 통과하면 방문 처리를 하고, dfs를 호출한다.

그리고 다음 방문을 위해 꼭 방문 처리를 0으로 돌려 놓아야한다.

 

 

📌  문제 코멘트

전반적인 dfs는 다 구현을 했는데, 부등호 부분을 어떻게 처리해야 할 지 몰랐다.

 

조건문으로 해볼려 했는데, 너무 복잡해지는 것 같아서 안했다.

근데 막상 보니 생각보다 훨씬 간단했다. 

 

 DFS는 기본이고, 너무 많은 수가 반복 될 때는 백트레킹으로 가지치기를 하자 ! 

부등호 같은 조건도 True / False 정도만 리턴 받아도 훨씬 쉽게 가능하다. 

 

그리고 모든 DFS 백트래킹의 핵심은 depth(깊이)를 이용한 탈출 조건 !

---

📚문제

두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자. 

A ⇒ < < < > < < > < >

부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다. 

3 < 4 < 5 < 6 > 1 < 2 < 8 > 7 < 9 > 0

이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다. 그런데 주어진 부등호 관계를 만족하는 정수는 하나 이상 존재한다. 예를 들어 3456128790 뿐만 아니라 5689023174도 아래와 같이 부등호 관계 A를 만족시킨다. 

5 < 6 < 8 < 9 > 0 < 2 < 3 > 1 < 7 > 4

여러분은 제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다. 앞서 설명한 대로 각 부등호의 앞뒤에 들어가는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다. 

입력

첫 줄에 부등호 문자의 개수를 나타내는 정수 k가 주어진다. 그 다음 줄에는 k개의 부등호 기호가 하나의 공백을 두고 한 줄에 모두 제시된다. k의 범위는 2 ≤ k ≤ 9 이다. 

출력

여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다. 

예제 입력 1 복사

2
< >

예제 출력 1 복사

897
021

예제 입력 2 복사

9
> < < < > > > < <

예제 출력 2 복사

9567843012
1023765489