백준 알고리즘 문제 풀이 2529번: 부등호 ( Python)

백준 알고리즘(BOJ) 2529번 부등호 문제

• 문제 출처
  https://www.acmicpc.net/problem/2529

---

---

문제 풀이 방법

---

처음에는 단순하게 itertools라이브러리를 이용해서 주어진 부등호의 개수 k가 주어지면 0~9까지 들어있는 리스트(변수명 : lst) 중에서 k+1개의 순열을 구하는 방식으로 구한 후 부등호 리스트에서 꺼내서 각각 비교하는 방식으로 구현했다.

## 대략 이런식으로 구현할려고 함
lst = [i for i in range(10)]
arr = list(itertools.permutations(lst,k+1))

-> 알고는 있었지만 이렇게 하게 되면 시간 초과 및 메모리 초과로 통과할 수 없게 된다.

---

정석적인 구현 방식

• 재귀 함수를 이용하여 구현한다.

n = int(input())
arr = input().split()
chk = [False for i in range(10)]
mn,mx = '',''

def checkFunc(i,j,test):
  if test == '<':
    return i<j
  else:
    return i>j

def sol(cnt,text):
  global mn
  global mx
  if cnt == n+1:
    if len(mn) == 0:
      mn = text
    else:
      mx = text
    return
  for i in range(10):
    if chk[i] == False:
      if cnt == 0 or checkFunc(int(text[-1]),i,arr[cnt-1]):
        chk[i] =True
        sol(cnt+1,text+str(i))
        chk[i] = False

sol(0,"")
print(mx)
print(mn)

---

코드 설명

## 두개의 숫자와 부등호를 인자로 받아 
## 부등호에 따라서 두 숫자의 관계가 올바른지 체크 후 반환해준다. 
def checkFunc(i,j,test):
  if test == '<':
    return i<j
  else:
    return i>j

## cnt 는 부등호의 개수가 k개라면 숫자 문자열 길이는 k+1이기 때문에 체크용
def sol(cnt,text):
  global mn
  global mx
  if cnt == n+1:
    if len(mn) == 0:
      mn = text ## 처음 출력되는 숫자 문자열이면 최솟값
    else:
      mx = text ## 계속 덮어써져서 마지막에 문자열은 최대값이 됨
    return
  for i in range(10): ## 0부터 9까지 반복문
    if chk[i] == False: ## 아직 안쓰인 숫자인지 체크
      if cnt == 0 or checkFunc(int(text[-1]),i,arr[cnt-1]):
        chk[i] =True ## 사용한 숫자 체크 
        sol(cnt+1,text+str(i)) ## 조건이 True인 숫자를 숫자 문자열에 더해줌
        chk[i] = False ## 재귀에서 빠져나가면 다시 돌려준다.

• sol함수에서는 반복문에서 0부터 시작했기 때문에 처음 조건과 맞아 출력되는 문자열은 최솟값을 가지게 되는 숫자 문자열이 되고
  계속 조건에 맞는 문자열이 출력되는데 이를 mx(최대 숫자 문자열)에 덮어씌어 저장해서 결국에는 가장 마지막에 값이 mx에 저장되게 된다.

---

• 아직도 재귀를 사용한 문제 풀이에는 익숙치가 않아서 자꾸 헷갈려서 라이브러리를 사용하려고 한다.

• 재귀와 DFS, BFS문제를 지속적으로 많이 풀어봐야겠다.

2021.08.19일 기준 BOJ 문제 91문제 해결

-> 방학이 끝나기 전에 100문제 풀이 채울 수 있을거 같다.