주어진 자릿수로 만들 수 있는 최대/최소의 수 구하기

예를 들어 N의 자릿수를 가지는 최대/최소의 수를 구한다고 해 보자. 제약 조건은 숫자는 겹치면 안되고, 0으로 시작하면 안된다. 이럴 때 N이 3일 경우 가질 수 있는 최대의 수는 987이 되고 최소한의 수는 102가 된다.

이를 파이썬으로 구하기 위해서 다음과 같이 코드를 작성할 수 있다.

import string
from itertools import permutations

n = int(input())

upper = (10 ** (n))
lower = int(10 ** (n -1))

f = [int("".join(x)) for x in permutations(string.digits, n) if lower < int("".join(x)) < upper]
s = sorted(f)

print(f[0], f[-1])

우선 이 문제를 풀기 위해서는 이런게 필요한 것 같다.

  1. n의 자릿수가 가질 수 있는 상한과 하한 구하기
  2. 상한과 하한 사이에서 조합할 수 있는, 중복 없는 캐릭터의 조합
  3. 정렬

N의 자릿수를 가지는 숫자의 집합은 문자의 조합으로 만들어내는 것이 편한 것 같다. 숫자로만 하기에는 조건 등을 계산하기가 매우 어려워 보이고, 문자의 조합을 통해 만들어낸 문자열을 숫자로 변환하면 001같은 경우 1로 변환되므로, 상하한 필터링도 쉽게 된다.

문자 교환하기

예를 들어 ACGT, DNA를 교환하는 문제에 대해 생각해 보자. DNA는 네 가지의 염기를 가지는데 각각 A, C, G, T가 된다. …

어쨌든 이 문제에서는 A는 T로, C는 G로만 변화한다고 했을 때 주어진 염기 서열을 교환하면 어떻게 변화하겠냐는 것을 묻는 문제였다.

가장 간단한 풀이 해법으로는 딕셔너리를 만들고 키에 대응하는 값을 대신 출력하는 것으로 이 문제를 해결할 수 있다.