99클럽 TIL (240827)

> [Middler] 부등호

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

 

🔥 다시 풀기 🔥

 

 

문제 풀이 과정

이러한 문제 유형을 어려워 한다. 처음 생각은 0부터 10 숫자를 돌면서 이전 숫자와 비교했을 때, 부등호가 맞다면 큐에 계속 적재하고 아니면 맞을때까지 큐를 팝한다는 생각을 했으나 지속되는 index range error로... 풀지 못함.

 

검색해보니 백트래킹 + 완탐으로 문제를 해결한 것을 알게되어 코드를 참조했다. 완벽히 이해가 가지 않아 백트래킹을 다시 공부했다.

 

✨ 백트래킹

현재 상태에서 가능한 모든 후보군에 따라 들어가며 탐색하는 알고리즘. 

주로 재귀의 형태로 코드를 구현, 기본 틀을 두는 편이 좋다.

 

문제 풀이

python

• check(왼쪽 숫자, 오른쪽 숫자, 부등호) 
  • 왼쪽 숫자 : s에 마지막에 넣어준 숫자
  • 오른쪽 숫자 : s에 넣어준 숫자 다음 숫자, 즉 현재 i
  • 부등호 : 현재 탐색에서 검사하고 있는 숫자

k = int(input()) # 2
signs = input().split() # 2
nums = [i for i in range(9)]
v = [0] * 10

def check(x,y,k) :
    if k == "<" :
        return x < y
    else :
        return x > y
        
ans = []

def solve(idx, s) :
    global mx, mn
    if idx == k+1 :
        ans.append(s)
        return
        
    for i in range(10) :
        if not v[i] :
            if idx == 0 or check(s[-1], str(i), signs[idx-1]) :
                v[i] = True
                solve(idx+1, s + str(i))
                v[i] = False
                
solve(0,'')
print(ans[len(ans)-1])
print(ans[0])

 

회고 및 느낀점

이해....해야한다...