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

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

 

Difficulty : Silver 1

 

Status : Solved

 

Time : 00:13:50

 

---

 

문제 설명

 

두 종류의 부등호 기호 ‘<’와 ‘>’가 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인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다. 

 

입력 예시

2
< >

 

출력 예시

897
021

 

 

---

 

풀이

 

dfs로 풀이해보자. 직전의 값이 prev_num라면, 참조하는 현재 부등호에 따라 다음 탐색값이 달라진다.

 

• '<' : prev_num + 1 부터 9까지
• '>' : prev_num - 1 부터 0까지

 

이 중 '아직 방문하지 않은 값'에 대해 방문 리스트를 업데이트하고 다음 인덱스로 탐색을 진행하면 된다. 만약 끝부분까지 도달이 가능한 경우(탐색이 완료한 경우) 결과를 저장한다. 이런 식으로 모든 경우에 대해 순환을 끝내고 나면 가능한 모든 경우의 수가 저장되어 있으니, 이 중 최댓값과 최솟값을 뽑아내면 된다.

 

• init : 전체 부등호 N과 부등호 리스트 ineq_list를 입력받아 반환한다.
• make_num : visited에 저장된 방문 순서를 통해 최종 출력값을 도출하여 문자열의 형태로 변환한다.
• dfs : 재귀적으로 호출되며 DFS를 시행하는 탐색 함수. 위 알고리즘에서 설명한 대로 동작한다. 만약 인덱스의 끝까지 도달한다면 make_num 함수를 호출하여 반환된 결과물을 전역 리스트 result에 저장한다.
• result_out : 전역 리스트 result를 정렬하고, 최댓값과 최솟값을 출력한다.
• solve : 메인함수. init을 호출하여 부등호 리스트를 반환받는다. 총 10번의 순환동안, 초기값을 세팅하고 dfs함수에 ineq_list를 전달한다. 순환 종료 후 result_out함수를 이용하여 결과물을 출력한다.

 

 

풀이 코드

 

visited = [-1]*10
result = list()

def init() :
  global N
  N = int(input())
  ineq_list = list(input().split())
  return ineq_list

def make_num() :
  result = [0]*(N+1)
  for i in range(10) :
    if visited[i] > -1 :
      result[visited[i]] = str(i)

  return ''.join(result)

def dfs(prev_num, ineq_list, idx) :
  if idx == N+1 :
    result.append(make_num())
    return

  if ineq_list[idx-1] == '>' :
    _range = range(prev_num-1, -1, -1)
  else :
    _range = range(prev_num+1, 10)

  for i in _range :
    if visited[i] == -1 :
      visited[i] = idx
      dfs(i, ineq_list, idx+1)
      visited[i] = -1

def result_out() :
  result.sort()
  print(result[-1])
  print(result[0])

def solve() :
  ineq_list = init()
  for i in range(10) :
    visited[i] = 0
    dfs(i, ineq_list, 1)
    visited[i] = -1
  result_out()

solve()

풀이 완료~