[코테챌린지] 부등호

📌 구해야 하는 정답

• k개의 부등호가 주어집니다. (예: 3개의 부등호 -> 4개의 숫자가 필요)
• 부등호의 순서를 만족하는 최대값과 최소값을 구하는 문제입니다.

📌 풀이

• 숫자의 순열을 생성:
  • 주어진 부등호에 맞는 숫자 조합을 찾기 위해 0부터 9까지의 숫자 중에서 필요한 개수만큼 순열을 생성합니다.
• 부등호 조건을 만족하는지 확인:
  • 각 순열에 대해 부등호 조건을 확인하고, 부등호 조건을 만족하면 그 순열을 사용합니다.
• 최대값과 최소값을 구함:
  • 조건을 만족하는 숫자 중에서 가장 큰 값과 작은 값을 찾아 출력합니다.
• 순열을 이용하는 경우, 시간 복잡도는 O(n!) 가 됩니다.
  • 예를 들어, k=9일 경우에는 10개의 숫자 중에서 순열을 구하는 방식이므로, 최대 10!이 발생할 수 있습니다.
  • 10!=3,628,800 이므로 충분히 풀 수 있는 범위입니다.
• 조건을 만족하지 않는 순열은 빠르게 탐색을 종료합니다(백트래킹).
• 주어진 부등호가 많지 않기 때문에 10!은 충분히 계산할 수 있습니다.

📌 코드 설계

1. 입력: 부등호 개수 k와 부등호의 형태를 입력받습니다.
2. 순열 생성: itertools.permutations를 사용하여 0∼9까지의 숫자 중에서 k+1개의 숫자를 뽑아 모든 순열을 만듭니다.
3. 부등호 체크: 각 순열이 주어진 부등호 조건을 만족하는지 확인합니다. 조건을 만족하는 경우 해당 순열을 기록합니다.
4. 최대값과 최소값 갱신: 조건을 만족하는 순열 중 가장 큰 값과 작은 값을 기록합니다.
5. 결과 출력: 최종적으로 최대값과 최소값을 출력합니다.

📌  정답코드

from itertools import permutations

# 부등호 갯수 입력
k = int(input())

# 부등호 입력
signs = input().split()

# 0부터 9까지의 숫자 중에서 (k + 1)개의 숫자 순열 생성
numbers = [i for i in range(10)]

# 부등호 조건을 확인하는 함수
def check(perm, signs):
    for i in range(len(signs)):
        if signs[i] == '<' and perm[i] > perm[i + 1]:
            return False
        elif signs[i] == '>' and perm[i] < perm[i + 1]:
            return False
    return True

min_val, max_val = None, None

# 주어진 k+1 자리 순열을 모두 확인
for perm in permutations(numbers, k + 1):
    if check(perm, signs):  # 부등호 조건 만족 여부 체크
        perm_str = ''.join(map(str, perm))
        if min_val is None or perm_str < min_val:
            min_val = perm_str
        if max_val is None or perm_str > max_val:
            max_val = perm_str

# 결과 출력
print(max_val)
print(min_val)