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

 

 

 

 

 

 

 

 

 

 

📝 문제 분석

 

 

이 문제는 k개의 부등호 기호(<, >)가 주어졌을 때 주어진 부등호 관계를 만족하는 k+1 자리의 최댓값과 최솟값을 찾는 문제입니다. 

 

 

 

✅ 문제 조건

• 사용할 숫자
  • 0부터 9까지의 숫자 중에서 서로 다른 숫자를 선택해야 합니다.
  • 즉, 한 번 사용한 숫자는 다시 사용할 수 없습니다.
• 부등호 관계
  • 주어진 k개의 부등호 기호에 맞게 숫자를 배치해야 합니다.
  • 예를 들어, 부등호가 < > 라면, 3 < 5 > 2 같은 식으로 숫자를 배치해야 합니다. 
• 목표
  • 가능한 숫자 조합 중에서 가장 큰 값과 가장 작은 값을 찾아야 합니다. 

 

 

 

 

 

1️⃣ 예제 1

# 입력
2
< >

# 출력
897
021

• k = 2 → 2개의 부등호가 주어짐
• < > → 첫 번째 숫자 < 두 번째 숫자 > 세 번째 숫자의 관계를 만족해야 함

 

• 가능한 숫자 조합
  • 0 < 2 > 1 → 021 (최솟값)
  • 1 < 3 > 0 → 130
  • 2 < 3 > 1 → 231
  • 7 < 9 > 8 → 798
  • 8 < 9 > 7 → 897 (최댓값)

 

 

 

 

 

 

 

 

 

 

💡 해결 방법

 

이 문제는 백트래킹(Backtracking)을 사용하여 문제를 해결할 수 있습니다.

 

 

 

 

 

📌 백트래킹(Backtracking)이란?

 

백트래킹은 가능한 모든 조합을 탐색하면서 조건을 만족하지 않는 경우 즉시 되돌아가는 방식입니다. 

 

 

✅ 동작 방식

1. 가능한 숫자를 하나 선택합니다.

2. 이전에 선택한 숫자와 비교하여 부등호 관계를 만족하는지 확인합니다.

3. 조건을 만족하면 다음 숫자를 선택하고 그렇지 않으면 되돌아갑니다.

4. k+1 개의 숫자를 모두 선택하면 최댓값과 최솟값을 갱신합니다.

5. 모든 경우를 탐색한 후 최종 결과를 출력합니다. 

 

 

 

 

 

1️⃣ Step 1: 가능한 모든 숫자 조합을 생성

 

0 ~ 9 사이의 숫자 중에서 서로 다른 k+1 개의 숫자를 선택해야 합니다. 즉, 같은 숫자는 한 번만 사용할 수 있으며 백트래킹을 이용하여 모든 조합을 탐색해야 합니다. 

 

 

 

✅ 숫자 방문 여부 체크

visited = [False] * 10

• visited[i] = True 로 설정하면 해당 숫자를 선택했음을 의미합니다.
• 백트래킹이 끝나면 visited[i] = False로 되돌려 다시 선택할 수 있도록 합니다.

 

 

 

 

 

2️⃣ Step 2: 선택한 숫자가 부등호 관계를 만족하는지 검사

 

각 숫자는 이전 숫자와 부등호 관계(<, >)를 만족해야 합니다. 

• <: 이전 숫자 < 현재 숫자
• >: 이전 숫자 > 현재 숫자

 

 

 

✅ 부등호 관계 검사

def check(a, b, sign):
    return a < b if sign == '<' else a > b

 

 

 

 

 

 

3️⃣ Step 3: 백트래킹 수행

 

숫자를 선택할 때마다 사용 여부를 체크하고 탐색이 끝난 경우 다시 사용 가능하도록 복구합니다. 

    for i in range(10):  # 0~9까지 숫자를 탐색
        if not visited[i]:  # 아직 사용되지 않은 숫자인 경우
            if depth == 0 or check(int(s[-1]), i, signs[depth-1]):  # 부등호 조건 검사
                visited[i] = True  # 숫자 사용 처리
                solve(depth+1, s+str(i))  # 다음 숫자 선택
                visited[i] = False  # 백트래킹 (되돌아가기)

• for i in range(10): 0부터 9까지 하나씩 선택하며 탐색합니다.
• if not visited[i]: 이미 선택한 숫자는 다시 사용할 수 없으므로 중복을 방지합니다.
• if depth == 0 or check(int(s[-1]), i, signs[depth-1])
  • 첫 번째 숫자는 무조건 선택할 수 있습니다.
  • 이후부터는 이전 숫자(s[-1])와 현재 숫자(i)가 주어진 부등호 관계를 만족하는지 검사해야 합니다.
• visited[i] = True: 숫자를 사용했다고 표시하여 중복 선택을 방지합니다.
• solve(depth+1, s+str(i)): 다음 숫자를 선택하기 위해 재귀 호출합니다.
• visited[i] = False: 탐색이 끝난 후 다른 조합을 만들기 위해 다시 숫자를 사용 가능하도록 복구합니다. 

 

 

 

 

 

4️⃣ Step 4: 최댓값과 최솟값을 갱신

 

숫자를 선택하며 k+1개의 숫자가 완성되면 최댓값과 최솟값을 갱신합니다.

    if depth == n + 1:
        if max_ans is None or s > max_ans:
            max_ans = s  # 최댓값 갱신
        if min_ans is None or s < min_ans:
            min_ans = s  # 최솟값 갱신
        return

• depth == n + 1: 모든 숫자를 선택한 경우이므로 최댓값과 최솟값을 갱신합니다.
• max_ans와 min_ans는 문자열 비교를 이용하여 갱신합니다.
  • 예를 들어, "897"과 "021"을 비교하면 "897"이 더 크므로 최댓값이 됩니다. 

 

 

 

 

👩‍💻 나의 답안

def check(a, b , sign):
    return a < b if sign == '<' else a > b

def solve(depth, s):
    global max_ans, min_ans

    if depth == n + 1:
        if max_ans is None or s > max_ans:
            max_ans = s
        if min_ans is None or s < min_ans:
            min_ans = s
        return

    for i in range(10):
        if not visited[i]:
            if depth == 0 or check(int(s[-1]), i, signs[depth-1]):
                visited[i] = True
                solve(depth+1, s+str(i))
                visited[i] = False


n = int(input())
signs = input().split()

visited = [False] * 10
max_ans = None
min_ans = None

solve(0, "")
print(max_ans)
print(min_ans)

 

Algorithm/백준/Silver/2529. 부등호 at main · kuun1000/Algorithm