[코테]99클럽 코테 스터디 24일차 TIL 백준 2529 부등호

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

일단 이 문제는 처음 보자마자 bruteforce 일것 같다라는 생각이 들었었다. 그런데 조금 더 생각해 보니 모두 다 탐색할 필요 없이 중간에 부등호에 맞지 않는 숫자배열이 나온다면 멈추는 알고리즘, 즉 백트래킹을 사용해야할 것 같다는 생각이 들었다..! 

먼저 문자 부등호를 입력받아서 값을 비교하는 로직을 하나 짜고, 백트래킹 알고리즘을 활용하였다..!

최댓값, 최솟값만 구하면 되기 때문에 부등호에 맞는 가장 처음과 가장 마지막 숫자 배열을 프린트 해주기 위하여 함수를 두개 짰다.

주의할 점은, visited 와 global 변수 found를 max값 구하는 함수와 min값 구하는 함수에 각각 초깃값을 다르게 해주어야한다는 점이다. 

import sys

read = sys.stdin.readline

k = int(read().rstrip())

inequality = list(map(str, read().split()))

# 문자 부등호를 이용해서 값 비교하기

def str2real(inequal, nums):

    for i in range(k):

        if inequal[i] == '<' and nums[i] >= nums[i+1]:

            return False

        if inequal[i] == '>' and nums[i] <= nums[i+1]:

            return False

    return True  

visited = [False] * 10

ex_nums = [i for i in range(10)]

answer_min = []

answer_max = []

found_min = False

found_max = False

def find_min(depth):

    global found_min

    if found_min:

        return

    if depth == k + 1:

        if str2real(inequality, answer_min):

            print(''.join(map(str, answer_min)))

            found_min = True

        return

    for i in range(10):

        if not visited[i]:

            visited[i] = True

            answer_min.append(i)

            find_min(depth+1)

            visited[i] = False

            answer_min.pop()

def find_max(depth):

    global found_max

    if found_max:

        return

    if depth == k + 1:

        if str2real(inequality, answer_max):

            print(''.join(map(str, answer_max)))

            found_max = True

        return

    for i in range(10):

        if not visited[i]:

            visited[i] = True

            answer_max.append(ex_nums[9-i])

            find_max(depth+1)

            visited[i] = False

            answer_max.pop()

find_max(0)

visited = [False] * 10

find_min(0)