[BOJ/백준] 16719 ZOAC 파이썬

문제 링크 : https://www.acmicpc.net/problem/16719

16719번: ZOAC

나는 진행을 거꾸로했다.

완성된 문자열에서 하나씩 지워가면서 체크했다.

문자를 중간에 끼워넣고 하는 아이디어가 잘안떠올라서 그냥 거꾸로 진행했다.

 

처음에는 입력으로 들어온 문자열을 가지고 시작하며 정답 배열에 입력 문자열을 저장해놓자.

다음부터는 결과의 마지막 문자열을 가지고 수행한다.

 

우선 현재 문자열을 리스트로 바꿔서 두개의 리스트에 저장했다.

 

하나는 현재 기준으로 문자 하나를 뺐을 때 사전순으로 가장 먼저오는 단어를 저장한 것이다. 이를 가지고 비교를 해서 갱신한다.

두번째는 위의 배열과 비교할 배열이다.

 

첫번째를 A 두번째를 B라고 해보자

 

입력이 ABC가 들어왔다고 해보자.

처음에는 가장 앞의 단어를 지운다.

그래서 A는 ['',B,C], B는 [A,B,C]가 된다.

다음 두번째부터는 B에서 문자를 지우고 A와 비교한다.

두번째 문자를 지워보자

A : ['',B,C] -> BC

B : [A,'',C] -> AC

B의 문자가 A보다 사전순으로 앞서니 A를 B의 형태로 바꾸고 B는 원래대로 돌려놓자.

그럼 A는 [A,'',C]가 된다.

 

다음은 세번째 문자를 지워보자

A : [A,'',C] -> AC

B : [A,B,''] -> AB

B의 문자가 A보다 사전순으로 앞서니 A를 B의 형태로 바꾸고 B는 원래대로 돌려놓자.

그럼 A는 [A,B,'']가 된다.

 

끝에 까지 도달했다면

A 배열을 문자열로 바꿔서 정답 배열에 저장하자.

그럼 다음 문자열은 AB가 되고 위의 과정을 다시 수행하면 된다.

 

그럼 정답 배열에는 [ABC,AB,A]가 저장될 것이다.

이를 역으로 출력하면 정답이 된다.

그리고 맨 마지막에는 공백 문자가 들어가게 되므로 반복문 길이를 하나 줄이던가 출력시 하나 건너띄고 출력하면 된다.

 

alpha = input().strip()

def solv():
    answer_list = [alpha]
    answer = alpha
    for _ in range(len(answer)):
        tmp1 = list(answer)
        tmp2 = list(answer)
        target_idx = -1
        for idx in range(len(answer)):
            if target_idx == -1:
                tmp1[idx] = ''
                target_idx = idx
            else:
                tmp2[idx] = ''
                str_tmp1,str_tmp2 = ''.join(tmp1),''.join(tmp2)
                if sorted((str_tmp1, str_tmp2))[0] == str_tmp2:
                    tmp1[target_idx] = answer[target_idx]
                    tmp1[idx] = ''
                    target_idx = idx
                tmp2[idx] = answer[idx]
        answer = ''.join(tmp1)
        answer_list.append(answer)
    answer_list.reverse()
    for ans in answer_list[1:]:
        print(ans)
solv()