❓2529번 : 부등호
📈 문제 요약
두 종류의 부등호 ‘<’, ‘>’가 N개 주어질 때 이 부등호 기호 앞 뒤에 서로 다른 한 자릿 수 숫자를 넣어 모든 부등호 관계를 만족시키는 최대값, 최소값을 각각 구하면 되는 문제
🤨 접근법
해당 문제가 그리디 알고리즘 유형이라고 소개되어 이를 알고 풀이했지만 왜 그리디 알고리즘이지? 하면서 백트래킹으로 풀이 하였다. 알고보니 백트래킹 방법에서도 그리디한 방법으로 구현해야했기 때문이었다.
왜 그리디한 백트래킹이냐! 부등호 사이사이에 수를 하나씩 넣어볼 때 0 → 9까지 순서대로 넣어보기 때문에 최소값을 찾는 측면에서 특정 순간의 최적의 방법인 넣을 수 있는 수 중 최소인 값을 넣어보는 것이 바로 그리디한 방법인 것이다. 평소 무심코 백트래킹에서 사용하는 방법이지만 이러한 측면에서 보니 그리디한 방법이 맞았다.
아무튼, 0 → 9까지 순서대로 부등호 사이사이에 해당하는 수들을 공백 문자열에 추가하는 재귀 함수를 활용했고, 수를 넣을 때 마다 해당 위치의 부등호 조건에 맞는지 검사해 조건에 맞지 않는다면 해당 가지를 잘라냈다.
이렇게 순서대로 값을 넣어본다면 결국 가장 먼저 만들어지는 문자열이 만들 수 있는 최소의 형태를 띤다. 0이 맨 앞으로 와도 되기 때문에 문자열의 형태로 나타내어야 편리하다.
그렇다면 반대로 9 → 0 순서대로 넣어서 가장 먼저 만들어지는 문자열이 최대의 형태를 띨 것이다. 이러한 점 때문에 그리디한 것이다.
나는 별도의 최대값을 구하는 함수를 정의하지 않고, 0→9 순서대로 접근하여 만들어내는 가장 마지막 수를 최대값으로 활용했다. 아마 문제에서 그리디한 점을 조금 더 강조했다면 이 부분을 시간초과나 메모리 초과로 막았을 것이다.
또한 그냥 백트래킹으로 가지를 쳐내지 않고 모든 경우를 고려하는 완전탐색이나 itertools의 순열을 활용한 풀이도 통과하는 문제였다고 한다.
🔡 코드
import sys
input = sys.stdin.readline
def check(tmp, i):
if i < 2:
return True
if operators[i-2] == '<':
if tmp[i-2] < tmp[i-1]:
return True
else:
if tmp[i-2] > tmp[i-1]:
return True
return False
def dfs(result):
i = len(result)
if not check(result, i):
return
if i == k+1:
results.append(result)
return
for num in numbers:
if not visited[int(num)]:
visited[int(num)] = True
dfs(result+num)
visited[int(num)] = False
numbers = list('0123456789')
k = int(input())
operators = input().rstrip().split()
result = ''
results = []
visited = [False for _ in range(10)]
for num in numbers:
visited[int(num)] = True
dfs(result+num)
visited[int(num)] = False
print(results[-1], results[0])numbers 배열에는 0 → 9 순서대로 숫자 문자가 담겨있고, 공백 문자에 순서대로 하나씩 넣어보며 재귀 함수(dfs)를 실행한다.
이때 재귀함수 내부에서 check함수로 부등호 조건에 맞는지 검사하는데, 로직은 문자열의 길이를 인자로 넘겨주어 이에 해당하는 부등호를 참조해 부등호 양쪽의 숫자가 적절하게 배치되었는지를 검사한다. 문자열의 길이가 2보다 작으면 그냥 넘어가는 이유는 두 수를 비교하려면 당연히 수 두개가 있어야 하기 때문이다.
아무튼 조건에 맞아서 특정 문자가 포함이 되었다면 다시 숫자를 넣어본다. 이 때 visited 배열을 활용해 이미 포함되어있는 숫자는 다시 포함되어지지 않도록 한다. 이 과정을 문자열의 길이가 부등호의 개수(k)+1이 될 때까지 반복하고, 무사히 해당 길이까지 숫자가 채워졌다면 results 배열에 추가한다.
최종적으로 results 배열에 가장 먼저 담긴 문자열이 가장 최소 값을 가지는 문자열이 되고, 가장 마지막에 담긴 문자열이 가장 최대 값을 가지는 문자열이 된다.
