[Implementation] 백준 16719번 “ZOAC” Python 풀이

문제 링크

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

풀이

• 정답을 출력할 배열을 만듭니다.
• 입력 문자열을 통해 아래 알고리즘을 진행합니다.
  • 입력 문자열에서 가장 작은 알파벳을 선택합니다.
  • 해당 알파벳을 정답 배열에 추가합니다.
  • 정답 배열의 모든 알파벳들을 취합해 출력합니다.
  • 해당 알파벳을 기준으로 뒷 문자열을 입력 문자열로 정해, 위 알고리즘을 반복합니다.
  • 해당 알파벳을 기준으로 앞 문자열을 입력 문자열로 정해, 위 알고리즘을 반복합니다.
• 현재 알파벳을 기준으로 뒷 문자열부터 확인한 뒤, 앞 문자열을 확인하는 이유는,
• 현재 알파벳이 입력 문자열에서 가장 작은 알파벳이기 때문에,
• 현재 알파벳이 가장 앞에 와야 가장 작아지기 때문입니다.
• 세부 알고리즘은 아래 예제 코드와 같습니다.

코드

import sys

# 문자열 입력
words = sys.stdin.readline().rstrip()

# 입력 문자열, 입력 문자열의 시작 인덱스
def solution(input_words, start_idx):

    # 전역 변수 수정 권한
    global result

    # 입력 배열이 비어있으면 리턴
    if input_words == "":
        return

    # 입력 문자열에서 가장 작은 문자 탐색
    min_char = min(input_words)
    # 가장 작은 문자의 인덱스 탐색
    min_char_idx = input_words.index(min_char)

    # 알파벳 위치(입력 문자열의 시작 인덱스 + 가장 작은 문자의 인덱스)에 알파벳 저장
    result[start_idx + min_char_idx] = min_char

    # 결과 배열 출력
    print(''.join(result))

    # 해당 문자 기준 뒷 문자열에 대해 위 함수 실행
    solution(input_words[min_char_idx + 1:], start_idx + min_char_idx + 1)

    # 해당 문자 기준 앞 문자열에 대해 위 함수 실행
    solution(input_words[:min_char_idx], start_idx)

# 결과 배열
result = [''] * len(words)

# 함수 호출 (입력 문자열, 입력 문자열의 시작 인덱스)
solution(words, 0)