[Python - Backtracking, Greedy] 2529 부등호

📌 문제

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

📌 문제 풀이

👨‍🏫 접근

백트래킹으로 푸는 게 좋을 것 같다. 매번 조건에 따라서 상황이 달라지고, 완전히 탐색해야 할 것 같고 백트래킹으로 값을 변경해가며 하는 것이 효율적일 것 같아서이다.

👨‍🏫 문제 풀이

📄 전체 코드

import sys
input = sys.stdin.readline


def solve(idx):  # idx는 부등호 위치, num은 들어갈 수
    if idx == k + 1:
        _num = ''.join(map(str, tmp))
        ans.append(_num)
        return

    for i in range(10):
        if not i in tmp:
            if idx == 0 or (opers[idx] == ">" and tmp[-1] > i) or (opers[idx] == "<" and tmp[-1] < i):
                tmp.append(i)
                solve(idx + 1)
                tmp.pop()


k = int(input())
opers = [""] + input().rstrip().split()
tmp = []

ans = []

solve(0)

print(ans[-1])
print(ans[0])

📄 준비

import sys
input = sys.stdin.readline

k = int(input())
opers = [""] + input().rstrip().split()
tmp = []

ans = []

opers는 부등호를 받을 변수이며, tmp는 백트래킹에서 사용할 임시 리스트 변수이다. ans는 가능한 부등호 수를 모두 모으기 위해 만든 리스트 변수이다.

📄 풀이

def solve(idx):
    if idx == k + 1:
        _num = ''.join(map(str, tmp))
        ans.append(_num)
        return

    for i in range(10):
        if not i in tmp:
            if idx == 0 or (opers[idx] == ">" and tmp[-1] > i) or (opers[idx] == "<" and tmp[-1] < i):
                tmp.append(i)
                solve(idx + 1)
                tmp.pop()

solve(0)

print(ans[-1])
print(ans[0])

모두 변수를 넣었으면 ans에 append 해주고 return 한다. 그렇지 않은 경우 반복문을 실행한다. 이때, 중복된 값이 들어가면 안돼서 in 연산자로 중복 여부를 판단했다.

 

중복되지 않는다면, 조건에 따라서 값을 넣어준다. 먼저 아무 것도 리스트에 없다면 바로 append 한다. 혹은 > 기호일 때, tmp의 마지막 값과 비교해서 대소 관계를 검사한다. 반대의 경우도 검사해준다. 만약 조건을 만족하면 값을 넣어주고 더 깊게 그래프를 탐색해준다.

 

반복을 0부터 9까지 하기 때문에 자동으로 오름차순으로 ans에 들어간다. 그래서 마지막 인덱스의 값과 첫 번째 인덱스의 값을 찾아서 출력해준다.

📌 총평

어려워 보였는데 의외로 엄청 쉬워서 당황쓰,,,

 

그런데 백트래킹 말고 그냥 반복문으로 푼 방법이 있어서 한 번 가져와봤다.

 

import sys
input = sys.stdin.readline


def getGreatestNum(ies):
    great = ['9']
    tmp = 0
    nums = [str(i) for i in range(9)]

    for i in ies:
        if i == "<":
            great.insert(tmp, nums.pop())
        else:
            great.append(nums.pop())
            tmp = len(great) - 1

    return ''.join(great)


def getSmallestNum(ies):
    small = ['0']
    tmp = 0
    nums = [str(i) for i in range(9, 0, -1)]

    for i in ies:
        if i == "<":
            small.append(nums.pop())
            tmp = len(small) - 1
        else:
            small.insert(tmp, nums.pop())

    return ''.join(small)


k = int(input())
ies = input().rstrip().split()

greatest_num = getGreatestNum(ies)
smallest_num = getSmallestNum(ies)

print(greatest_num)
print(smallest_num)

Greedy 하게 문제를 풀었다. 너무 신기하네..