[알고리즘/백트래킹] 2529번 : 부등호 - python

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

2529번: 부등호

 

---

• 문제
• 소요시간: 40분 26초

---

• 설계하기(접근방법) 

1. 입력받기

부등호를 입력받는다

 

2. 구현하기

완전탐색을 하려다가 시간초과가 날 것같아서 백트래킹을 했다

 

기존의 백트래킹 구조와 동일하지만

중간에 처리해주어야 할 문항들이 있다

 

부등호를 사용하는 조건이 있으니

중간중간 부등호 연산자를 통해 비교해주어

조건에 만족하면 다음단계로

만족하지 않는다면 이전 단계로 되돌아간다

 

operation = [<, < , >, >]와 같을 때

이전 숫자 3

현재 숫자 4 라면

3 < 4를 만족하기 때문에 pass

만약

2<4 라면 만족하지 못하기 때문에 되돌아간다

 

문제는 이전 숫자가 없는 cnt ==0 일때인데

cnt == 0 일 때 visited도 전부 0이기 때문에

그냥 for문과 dfs를 해준다

 

3. 출력하기

까다로운 점은 0으로 시작하는 숫자도 min 값으로 넣어야 한다는 점인데

이것은 list에 append 할 때

str로 변경해준 후 ''.join()을 진행해준다

 

 

---

• 코드(출력)

n = int(input())
# < > < >
operation = list(input().split())
# 0 1 2 3 4 5 6 7 8 9
visited = [0 for _ in range(10)]
result = []

def dfs(cnt,lst, before):
    if cnt == n + 1:
        lst = list(map(str, lst))
        lst = ''.join(lst)
        result.append(lst)
    else:
        if cnt == 0:
                for i in range(0, 10):
                    visited[i] = 1
                    dfs(cnt + 1,lst + [i], i)
                    visited[i] = 0
        else:
            for i in range(0, 10):
                if visited[i] == 0:
                    if operation[cnt - 1] == '>': 
                        if before > i:
                            visited[i] = 1
                            dfs(cnt + 1,lst + [i], i)
                            visited[i] = 0 
                    elif operation[cnt - 1] == '<':
                        if before < i:
                            visited[i] = 1
                            dfs(cnt + 1,lst + [i], i)
                            visited[i] = 0
                    

dfs(0,[],0)

print(max(result))
print(min(result))

---

• 얻어갈 부분

1. join 연산자는 str만 가능하다

2. max, min의 인자로 str도 받을 수 있다. 사전순으로 정렬된다

3. format의 경우 zfill()을 통해 앞을 0으로 채울 수도 있다