[백준 - Python] 2529. 부등호 (완전 탐색)

https://www.acmicpc.net/problem/2529

2529번: 부등호

 

코드

from itertools import permutations

n = int(input())
sign = list(map(str, input().split()))

ans = []
for c in list(permutations(range(10), n+1)):
    for i in range(len(sign)):
        if sign[i] == '<':  # 만족 하지 않는 경우 쳐내기
            if c[i] > c[i+1]:
                break
        else:
            if c[i] < c[i+1]:
                break
    else:  # 앞의 for 문에서 break 되지 않은 경우에만 실행  (for-else와 while-els)
        ans.append(c)
ans.sort()
print(''.join(map(str,ans[-1])))
print(''.join(map(str,ans[0])))

 

변수 n에 부등호 개수를 입력 받고

sign 변수에 부등호들을 저장한다.

 

순열 라이브러리인 permutations를 활용해 0~9까지의 숫자들 중에서

부등호 갯수보다 1개 많은 개수만큼의 순열을 뽑는다.

 

그 다음에 sign변수를 반복문을 돌면서,

해당 부등호와 그 부등호 앞뒤로 있는 숫자가 부등식을 만족하는지 확인하고

만족하지 않는 경우를 무시한다.

만족하는 경우에는 answer 변수에 저장한다

 

여기서 잠깐!

for-else문에 대해서 알아보자!

 

파이썬에서는 조건문에 else를 쓸 수 있듯이,

반복문에도 else를 쓸 수 있다

 

for문과 else문을 같이 쓰면,

for문에서 break문으로 탈출하지 않은 경우에만

else문이 실행된다.

 

따라서, ans.append(c)는 permutations(range(10), n+1)의 경우들 중

전제 sign과의 부등식을 확인해봤을 때,

부등식을 전부 만족하는 경우에만 수행이 된다

 

모든 경우들을 전부 확인한 후에

ans 리스트를 정렬해준 다음,

가장 큰 수와 가장 작은 수를 join 함수를 통해 구해준다.

 

 

참고 자료

https://wikidocs.net/190098

https://thought-process-ing.tistory.com/100