파이썬 백준 알고리즘: 부등호 2529

안녕하세요! 알고리즘 풀이 포스트를 작성할 개발자로 도움을 드릴게요. 이번에는 "부등호" 문제를 다루어보려고 합니다. 부등호 문제는 주어진 부등호 식에 맞게 숫자를 배열하여 만들 수 있는 가장 큰 수와 가장 작은 수를 찾는 문제입니다.

문제 내용

주어진 정수 k와 부등호 식을 활용하여 0부터 9까지의 숫자 중에서 서로 다른 숫자 k개를 골라서 부등호 식에 맞게 배열한 결과 중 가장 큰 수와 가장 작은 수를 찾는 문제입니다.

문제 이해하기

먼저, 입력으로 주어지는 값은 정수 k와 부등호 식을 담은 리스트입니다. 이 문제에서는 0부터 9까지의 숫자 중에서 서로 다른 숫자 k개를 골라서 부등호 식에 맞게 배열한 결과 중 가장 큰 수와 가장 작은 수를 찾아야 합니다.

주어진 문제를 풀기 위해 백트래킹(backtracking) 알고리즘을 활용합니다. 백트래킹은 해를 찾는 도중에 해가 아니라고 판단되는 경우 더 이상 해당 경로를 따라가지 않고 되돌아가는 기법입니다.

주어진 문제에서는 숫자를 하나씩 선택하면서 부등호 조건을 만족하는지 확인해야 합니다. 따라서 backtracking() 함수를 사용하여 숫자를 선택하고 조건을 확인하며 탐색을 진행합니다.

또한, 가장 큰 수와 가장 작은 수를 구하기 위해 전역 변수인 **MIN_NUM**과 **MAX_NUM**을 사용합니다. backtracking() 함수에서 조건을 만족하는 경우에만 **MIN_NUM**과 **MAX_NUM**을 업데이트합니다.

풀이 코드

pythonCopy code
MIN_NUM = 9999999999
MAX_NUM = 0

def backtracking(first, idx, answer):
    if idx == len(inequalities):
        global MIN_NUM, MAX_NUM
        answer = int(answer + str(first))
        if answer < MIN_NUM:
            MIN_NUM = answer
        if answer > MAX_NUM:
            MAX_NUM = answer
        return

    numbers[first] = True
    for second in range(10):
        if not numbers[second]:
            if inequalities[idx] == '<' and first < second:
                backtracking(second, idx + 1, answer + str(first))
            if inequalities[idx] == '>' and first > second:
                backtracking(second, idx + 1, answer + str(first))
    numbers[first] = False

k = int(input())
inequalities = list(map(str, input().split()))
numbers = [False] * 10  # 0 ~ 9

for i in range(10):
    backtracking(i, 0, '')

print(str(MAX_NUM).zfill(k + 1))
print(str(MIN_NUM).zfill(k + 1))

풀이 방법

1. backtracking() 함수를 사용하여 숫자를 선택하고 조건을 확인하는 백트래킹 알고리즘을 구현합니다.
2. **MIN_NUM**과 **MAX_NUM**을 전역 변수로 선언하여 가장 작은 수와 가장 큰 수를 저장합니다.
3. backtracking() 함수에서 주어진 부등호 조건에 따라 숫자를 선택하고 조건을 만족할 경우에만 **MIN_NUM**과 **MAX_NUM**을 업데이트합니다.
4. 모든 경우의 수를 탐색한 후, 가장 큰 수와 가장 작은 수를 출력합니다.

시간 복잡도

이 알고리즘의 시간 복잡도는 O(10!)입니다. 주어진 부등호 식에서 선택해야 하는 숫자는 0부터 9까지 10개입니다. 따라서 10개의 숫자 중에서 서로 다른 숫자 k개를 선택하는 모든 경우의 수를 탐색해야 합니다. 이는 O(10!)의 시간이 걸리며, 10!은 약 3,628,800입니다. 따라서 전체적인 시간 복잡도는 O(10!)입니다.

 

 

혹시 문제가 잘 안풀리고 답답하신가요? 아래를 눌러 백준 알고리즘 트랜드와 기출문제를 알아보세요! 이것만 알아도 네카라뿌십니다~

 

👉 백준 알고리즘 모음