부등호

문제

입력으로 부등호 기호 '<'와 '>'가 k개 나열된 순서열 A가 주어집니다.
k개의 부등호의 순서를 만족하는 k+1 자리의 정수중에서 최대값과 최소값을 찾아 출력하는 문제입니다.

제약조건

• 2 <= k <= 9
• 부등호 기호 앞뒤에 서로 다른 한자리수를 넣는다.
• 선택된 숫자는 모두 달라야한다.
• 첫자리가 0인 경우도 정답에 포함한다.

풀이

3 <= k+1 <= 10 . 즉 최대 10자리를 가집니다. 모든 경우의 수를 따져서 최대값 / 최소값을 구할수있습니다. 이 문제는 뽑는 순서에 따라 정답/오답으로 나뉩니다. 순서가 중요하므로 순열로 풀어야합니다.
"0123456789"중 k+1개를 뽑아 순열로 만들어 숫자를 만든 후 조건에 만족하는 경우를 모두 계산후 가장 큰 수와 작은수를 뽑아도 되지만 다음과 같은 방식으로 중간 과정을 생략할수가 있습니다. "9876543210"중 k+1개를 뽑아 만든 순열중 맨 처음에 발견된 순열은 최대값이 될것이며, "0123456789"중 k+1개를 뽑아 만든 순열중 맨 처음에 발견된 순열은 최대값이 될것입니다. 즉 최대값을 구한후 그 다음 순열에 대해 검증하는것이 아닌 최소값이 등장하는 위치로 바로 이동함으로써 중간 과정을 생략할 수 있습니다.

코드

'''
Created by jun on 21/05/18
'''
from itertools import permutations

def solve(number):
    for i in permutations(number, N+1):
        for idx in range(1, N+1):
            if sign[idx - 1] == '<' and i[idx - 1] > i[idx]:
                break
            elif sign[idx - 1] == '>' and i[idx - 1] < i[idx]:
                break
        else:
            return print(''.join(i)) #조건을 만족하면 바로 반환합니다.


N = int(input())
sign = input().split()
number = "0123456789"
solve(number[::-1]) #최대값 "9876543210"
solve(number) #최소값 "0123456789"

새로 알게된 사실

for else문에 대해 배웠습니다. for문이 도중에 끊기지 않고(break문) 종료됬을때 else문으로 들어갑니다. 기존 방식과는 다르게 flag를 사용하지 않고 구현이 가능합니다.