백준 16719 [ZOAC] 파이썬

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

 

진심 열받는 문제다.

 

 

 

# 백준 16719 ZOAC

import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

strings = list(map(str, input().rstrip()))


def like_zoac(string, prev_print, next_print):
    print_str = min(string)
    idx = string.index(print_str)
    print(prev_print + print_str + next_print)
    prev_string = string[:idx]
    if len(string) - 1 != idx:
        next_string = string[idx + 1 :]
    else:
        next_string = ""

    if next_string:
        next_strings = like_zoac(next_string, prev_print + string[idx], next_print)
        next_strings = next_strings[1:]
    else:
        next_strings = next_print

    if prev_string:
        like_zoac(prev_string, prev_print, string[idx] + next_strings)

    return prev_print + string[idx] + next_strings


like_zoac(strings, "", "")

좌 우로 나눠서 재귀로 풀려고 하는데 꼬였다.

 

# 백준 16719 ZOAC

import sys

input = sys.stdin.readline

s = list(input().rstrip())
n = len(s)


def solve(l, r, acc):
    if l >= r:
        return
    # 현재 구간 [l, r) 에서 사전순 최소 문자를 찾음
    idx = min(range(l, r), key=lambda i: s[i])
    acc[idx] = s[idx]
    print("".join(acc))
    # 오른쪽 먼저
    solve(idx + 1, r, acc)
    # 왼쪽 나중
    solve(l, idx, acc)


acc = [""] * n
solve(0, n, acc)

GPT 풀이를 첨부한다.

진짜 열받네