백트래킹, 브루트포스 알고리즘, 구현, 문자열
전형적인 백트래킹 문제라고 생각한다. 하지만 처리 과정이 살짝 난해한 점이 있었고 정렬 방식이 ASCII 순이라는 것도 조금 특이했던 것 같다.
Python의 Eval 함수를 사용하면 쉽게 해결할 수 있다고 봤는데 해당 방식을 사용하지 않고 정공법으로 해결하였다.
기본적으로 숫자의 합과 기존에 미처리된 숫자 2개를 들고 백트래킹을 진행하면서 '덧셈', '뺄셈', '연산하지 않음' 이 3가지 케이스에 대해서 전부 확인해준다는 생각으로 시도했고 맞았습니다를 받을 수 있었다.
# 0 만들기
import sys
input = sys.stdin.readline
def make_sum_zero(
result_arr: set,
target_arr: list,
last_index: int,
now_index: int = 0,
sum_now: int = 0,
now_calc: int = 0,
log=[],
) -> None:
"""
백트래킹을 활용하여 숫자들의 합이 0이 되도록 만드는 함수
"""
if last_index == now_index:
if not sum_now + now_calc:
result_arr.add("".join(log))
else:
if not now_index:
make_sum_zero(
result_arr,
target_arr,
last_index,
now_index + 1,
0,
target_arr[now_index],
[str(target_arr[now_index])],
)
else:
new_number = target_arr[now_index]
make_sum_zero(
result_arr,
target_arr,
last_index,
now_index + 1,
sum_now + now_calc,
new_number,
log + ["+", str(new_number)],
)
make_sum_zero(
result_arr,
target_arr,
last_index,
now_index + 1,
sum_now + now_calc,
-new_number,
log + ["-", str(new_number)],
)
if now_calc < 0:
make_sum_zero(
result_arr,
target_arr,
last_index,
now_index + 1,
sum_now,
10 * now_calc - new_number,
log + [" ", str(new_number)],
)
else:
make_sum_zero(
result_arr,
target_arr,
last_index,
now_index + 1,
sum_now,
10 * now_calc + new_number,
log + [" ", str(new_number)],
)
testcase = int(input())
output = []
for _ in range(testcase):
arr_length = int(input())
result = set()
# 함수를 통해 결과 확인
target_arr = [i for i in range(1, arr_length + 1)]
make_sum_zero(result, target_arr, arr_length)
# 혹여라도 겹치는 결과가 있다면 Set을 통해 배제, ASCII 순으로 정렬
sort_result = sorted(list(result), key=lambda x: ascii(x))
output.append(sort_result)
# 문제 조건에 맞춰 출력
for idx in range(testcase):
for element_idx in range(len(output[idx])):
print(output[idx][element_idx])
if idx != testcase - 1:
print("")