2529

날짜 : 2023. 05. 21

사용 언어 : python

 

문제

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

 

 

코드

import sys

def check(s, idx):  # 숫자, 체크할 인덱스
    # print(s)
    if idx == k:
        global max_val
        global min_val
        max_val = max(max_val, int(s))
        min_val = min(min_val, int(s))
    else:
        for i in range(10):
            if str(i) in s:  # 이미 숫자가 있는 경우
                continue # 패스
            else:
                if comp[idx] == '>' and int(s[-1]) > i:
                    check(s + str(i), idx+1)
                elif comp[idx] == '<' and int(s[-1]) < i:
                    check(s + str(i), idx+1)
    return


max_val = 0
min_val = 10e9

k = int(sys.stdin.readline())
comp = ' '.join(sys.stdin.readline().rstrip()).split()  # 부등호

for i in range(10):
    check(str(i), 0)
print(str(max_val))
print(str(min_val).zfill(k+1))

 

 

풀이

- 부등호가 k라면 숫자의 개수는 (k + 1) => 인덱스를 지정하면서 백트래킹을 실행한다.

- 넣을 수 있는 수는 0 ~ 9이고 각 for문을 돌리면서 입력받은 부등호마다 넣을 수 있는지 여부를 체크하면서 문자열에 붙인다.

- 방문여부를 체크할 때에는 0~9까지만 체크하기 때문에 그냥 in을 사용했다.

- 이후 길이가 맞았을 경우 전역변수를 활용해 최댓값, 최소값을 갱신한다.

 

 

알게된 점

- 인덱싱과 출력방식에서 오류가 떠서 조금 애먹었다.

- 인덱싱의 경우 처음 함수를 돌릴 때 아무것도 주지 않고 돌려버리니까 out of range에러가 떴다. 그래서 처음부터 0~9까지 넣고 돌리는 방식으로 푸니까 이건 해결됐다.

- 그리고 최소값의 경우에 int 형식으로 값을 비교해야 하기 때문에 앞에 있는 0은 저절로 절삭된다. 어차피 문자열로 출력해야 했고 그래서 앞에 0을 붙여서 출력하는 방식을 찾아보니 str(a).zfill(num) 함수가 있었다.

- 왠지 조합 문제다! 하면 이 문제를 떠올리면서 백트래킹, 재귀를 잘 떠올려봐야겠다.

 

 

참고 사이트

-