[알고리즘|파이썬] 백준 2529 부등호

문제 링크: https://www.acmicpc.net/problem/2529

📌 문제 탐색하기

시간 제한: 1초
메모리 제한: 256 MB

 

✏️ 구해야 하는 정답

두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열 A가 있다.

이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족할 때, 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다.

제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다

조건:

- 2 ≤ k ≤ 9

- 부등호 관계를 만족한다

- 각 부등호의 앞뒤에 들어가는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }

- 선택된 숫자는 모두 달라야 한다. 

- 출력 시 최대 정수를 첫째 줄, 최소 정수를 둘째 줄에 출력

- 첫자리가 0인 경우 0도 함께 출력 (예시: 023)

- 모든 입력에 답은 항상 존재

---

 

📌 풀이하기

완전탐색이 가능할까?

부등호의 개수 k의 범위는 2 ≤ k ≤ 9, 부등호 사이에 들어갈 수 있는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } 로 정해져 있으므로,

k 가 9로 정해지고, 숫자 10개를 모두 사용하여 모든 경우의 수를 만든다면, 10! 가지 수의 숫자를 만들 수 있다.

 

k = 2 인 경우,

부등호는 2개, 숫자는 3개, 나올 수 있는 숫자의 경우의 수는 10 * 9 * 8 = 720 개이다. 

(10 * 9 * 8 = 10! / (10-3)!)

 

10!/(10-k)! 개의 숫자는 k+1 자리 수의 숫자이기 때문에, 10!/(10-k)! 를 k 번 돌면서 두 개의 숫자가 부등호에 적합한 숫자인지 비교를 해야한다.

예를 들어 k = 2인 경우 부등호는 2개, 비교할 숫자는 3개 필요하므로 만들어지는 부등호 관계를 만족하는 정수는 3(=k+1)자리 수이다.

만들어 지는 3자리 정수는 아래 숫자들을 포함한 720개의 수가 된다.

nums : {987, 978, ..., 012}

이때 주어진 등호가 < 라고 했을때,

A < B 인지 확인을 하기 위해 아래와 같이 k 번의 loop를 돌면서 num[i], num[i+1]을 비교하게 된다.

for num in nums:
	for i in range(k):
    	if num[i] < num[i+1]:
        	# 조건 만족
        else:
        	# 조건 불만족

즉, len(nums) * k 만큼 연산을 하게 되는데, len(nums)는 10!/(10-k)! 이므로 완전 탐색을 하였을때 10!/(10-k)! * k 번의 연산을 하게 된다.

2 ≤ k ≤ 9 범위를 대입해서 계산해보면, 180 ≤ 10!/(10-k)! * k ≤ 32,659,200 범위가 되고, 이는 1초라는 제한 시간 안에 연산할 수 있는 범위이다. 

---

📌 코드 설계하기

1. input k, 부등호 k개 입력

2. { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } 로 10!/(10-k)! * k 개의 숫자 생성 (permutations로 순열 생성)

3. k 번 loop를 돌면서 num[i], num[i+1] 부등호 조건이 맞는지 확인

4. 부등호를 만족시키는 숫자 리스트 중 min, max 값 출력

---

📌 시도 회차 수정 사항

1회차: 시간 초과

부등호 확인 시 다음과 같은 코드를 돌게 구현하였다.

for num in nums:
    flag = True
    for i in range(k):
        if equations[i] == '<':
            if not num[i] < num[i + 1]:
                flag = False
        if equations[i] == '>':
            if not num[i] > num[i + 1]:
                flag = False
    if flag:
        satisfied_nums.append(num)

이때 flag가 중간에 False 로 바뀌어도 나머지 부등호 조건을 확인하므로 불필요한 연산이 추가가 되어 있었다.

flag = False인 경우 이후 부등호는 더 이상 볼 필요가 없으므로 break를 하도록 수정했다. 

 

수정된 코드:

for num in nums:
    flag = True
    for i in range(k):
        if equations[i] == '<':
            if not num[i] < num[i + 1]:
                flag = False
                break
        if equations[i] == '>':
            if not num[i] > num[i + 1]:
                flag = False
                break
    if flag:
        satisfied_nums.append(num)

---

📌 정답 코드

import itertools

k = int(input())
equations = list(input().split())
num_options = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
nums = list(itertools.permutations(num_options, k + 1))
satisfied_nums = list()


def toString(numList):
    answer = ""
    for n in range(len(numList)):
        answer += str(numList[n])
    return answer


for num in nums:
    flag = True
    for i in range(k):
        if equations[i] == '<':
            if not num[i] < num[i + 1]:
                flag = False
                break
        if equations[i] == '>':
            if not num[i] > num[i + 1]:
                flag = False
                break
    if flag:
        satisfied_nums.append(num)

print(toString(max(satisfied_nums)))
print(toString(min(satisfied_nums)))