[실버 1] 2529번: 부등호

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

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

---

사고의 흐름

• 출력 정수가 하나의 문자열이 되도록 해야 한다는 말은 답의 자료형이 정수형이 아니라 문자열이어야 한다는 뜻인가?
• 복잡해 보이지만 결국 부등호 1개를 중심으로 앞, 뒤의 숫자의 대소만 비교해주면 되는 문제이다.
• 만약 k가 9면 for문을 10개 돌려야 하나? 그건 미친 짓이야.
• 모든 숫자가 중복되지 않는 게 핵심일까? 중복을 허용할 때보다 가짓수가 훨씬 줄어드니까.
• 앞의 숫자와 부등호를 받은 다음 만약 < 이면 뒤 숫자를 앞 숫자보다 크게, >이면 작게 설정하고 나서 인덱스를 하나씩 올리면서 반복하면 되지 않을까?
• 근데 그러다가 가능한 가짓수가 없을 때는? 이전의 상황으로 되돌아가야 하겠는데. 스택 자료구조를 사용하는 재귀 함수를 쓰면 자연스럽게 구현이 가능할 것 같은데?
• 리스트는 Mutable하니까 재귀함수가 계속 호출되는 와중에 답을 찾았을 때도 탈출할 필요 없이 append() 메서드로 수정만 해주면 될 듯?
• 부등호는 한 번 받으면 수정할 필요 없으니까 튜플을 써도 되겠다.

 

• 재귀 함수로는 구현이 불가능하다. 숫자들의 중복 여부를 판별하기 위해서 이전의 숫자들과 현재 탐색 중인 숫자가 겹치는지 서로 확인을 해야 하는데, 재귀 함수를 사용하면 이전 함수 내의 변수 값들을 받아오기 어렵다.
• 아니면 집합을 하나 만들어서 숫자가 나왔는지 여부를 판단하면 되지 않을까? 집합이 Mutable하다면 가능할 듯.
• 집합도 Mutable한 자료형이구나! 그럼 가능하겠네.
• 답이 맞는 경우가 나오면 임시 리스트에 조각조각 저장된 숫자들을 정답 리스트에 하나의 원소로 만들어서 옮겨야 하는데 어떻게 하지?
• "".join() 메서드를 쓰면 되겠네. 어차피 답안도 문자열로 출력해야 하니 이 방법이 좋겠다.

내가 작성한 소스코드

import sys

def find_num(x, idx):
    temp.append(x)

    if idx == len(ineqs):
        ans.append("".join(map(str, temp)))
    else:
        if ineqs[idx] == '<':
            for i in range((x + 1), 10):
                if i not in num_check:
                    num_check.add(i)
                    find_num(i, idx+1)
                    num_check.remove(i)
        elif ineqs[idx] == '>':
            for i in range(0, x):
                if i not in num_check:
                    num_check.add(i)
                    find_num(i, idx+1)
                    num_check.remove(i)

    temp.pop()


k = int(sys.stdin.readline().rstrip())
ineqs = tuple(sys.stdin.readline().split())
num_check = set()
temp = []; ans = []

for i in range(10):
    num_check.add(i)
    find_num(i, 0)
    num_check.remove(i)

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

남이 작성한 소스코드

axcee 님:
https://www.acmicpc.net/source/6483480
rabin9948 님:
https://www.acmicpc.net/source/10642026

피드백

• operator 라이브러리에서 부등호 연산자를 가져와서 사용할 수 있다! 물론 조건문에 직접 부등호를 넣어 하드코딩할 때는 굳이 라이브러리를 사용할 필요가 없겠지만, 이번 문제처럼 Input에서 부등호를 Parsing해야 할 때는 유용하게 사용할 수 있다.
• 기본적으로 최솟값은 0, 1, 2, ... 순으로, 최댓값은 9, 8, 7, ... 순으로 숫자가 사용된다. 즉 K값에 따라 정답에 어떤 숫자들이 사용될지 미리 알 수 있다는 뜻이다. 그러므로 미리 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 리스트를 만들어 놓고 원하는 대로 Slicing해서 정답을 구하는 숫자 원소들로 사용할 수 있다.
  (이런 발상은 어떻게 하는지 모르겠다. 정말 대단하다.)
• 잘게 잘려서 하나씩 리스트에 보관된 숫자/문자열을 하나로 합쳐 얻고 싶을 때는 "".join() 메서드를 사용하자.