#1464 뒤집기 3

이 문제는 Gold V 문제입니다.

 

문자열이 주여졌을 때, 처음 1글자를 뒤집을 수도 있고, 아닐 수도 있습니다.  다음에는 처음 2글자를 뒤집을 수도 있고 아닐 수도 있죠.  이렇게 해서 총 글자수대로 뒤집을 수도 있고 아닐 수도 있습니다.

 

예를 들어서 "CDEFA" 란 문자열이 주어진다면,

 

1글자에서는 뒤집지 않는다를 선택하면 "CDEFA" 그대로 나오겠죠.

2글자에서 뒤집기를 한다면, "CD"가 뒤집혀서 "DCEFA"가 됩니다.

3글자에서 뒤집지 않는다를 선택하면 그대로 유지되고

4글자에서 뒤집기를 한다면, "DCEF"가 뒤집혀서 "FECDA"가 됩니다.

5글자에서 뒤집기를 한다면, "ADCEF"가 나옵니다.

 

이렇게 뒤집기를 선택했을 때 나올 수 있는 단어중 가장 앞에 나오는 단어를 얻도록 만드는 것이죠.

 

그러면 어떤 정책을 써야 이 문제를 풀기 쉬울까요?

"CADBAB"란 것을 생각해보죠.

C

A

D

B

A

B

가장 크게 뒤집기를 했을 때, 뒤에서 두번째 A가 가장 작죠.  분명히 여기서 뒤집기는 이루어질겁니다.

C

A

D

B

A

B

A

C

A

D

B

B

그러면 여기서 CABD중 작은 것을 찾게 되면 뒤에서 두번째 있는 A를 찾게 됩니다.

A

C

A

D

B

B

이거들을 또 뒤집기를 하면

A

A

C

D

B

B

이 됩니다.

 

마지막으로 C 하나만 남으니까, 더 이상 할 것이 없습니다.

 

이렇게 생각하면 매번 뒤집기를 해야 하니 어렵습니다.

뒤집기를 해야 하는 것을 살펴보면

1) CA.  2) ACDB. 3) BDCAA

형태입니다.

 

또 다른 예를 들자면,

"BACABAC" 문자열을 생각해보죠.

뒤에서부터 가장 작은 문자는 A이니,

A-BACAB-C

A-A-BAC-B-C

A-A-A-B-C-B-C

가 되죠.

 

이 알고리즘의 문제는 뒤에서부터 가장 작은 문자를 찾아야 한다는 것입니다.  기본적으로 \(O(N^2)\) 알고리즘이 됩니다.

뒤집기를 해도 어차피 순서를 유지하니, 앞에서부터 현재보다 작은 문자가 나오면 그것을 뒤로 놓는 방법을 생각해볼만합니다.

 

"CADBAB"라는 문자열이 있으면,

[C]ADBAB 로 C는 완성되었다고 봅니다.

그리고 C와 다음 글자 A와 비교해서 A가 C보다 작으므로 위치를 그대로 둡니다.

[CA]-DBAB

다음 글자 D는 A보다 크므로 위치를 바꿉니다.

D-[CA]-BAB

다음 글자 B도 A보다 크므로 위치를 바꿉니다.

BD-[CA]-AB

다음 글자 A는 A보다 크지 않으므로 위치를 그대로 둡니다.

BD-[CA-A]-B

B는 A보다 크므로 위치를 바꿉니다.

B-BD-[CA-A]

이것을 역순으로 하면 AACDBB가 되어 정답이 됩니다.

1) CA. 2) ACDB 3) BDCAA

형태로 자리바꿈을 하게 됩니다.

 

"BACABAC"라면

[B]ACABAC

[BA]CABAC

C-[BA]-ABAC

C-[BA-A]BAC

B-C-[BA-A]-AC

B-C-[BA-A-A]C

C-B-C-[BA-A-A]

그래서 정답은 AAABCBC가 됩니다.

뒤집기는

1) BA 2) ABC 3) CBAA 4) AABCB 5) BCBAAA

가 됩니다.

 

결국, 앞에서 했던 뒤에서부터 최소값을 검색하는 알고리즘의 역버전입니다.  완성된 문자열이라고 할 수 있는 [...]의 맨 뒤의 글자는 현재 완성된 문자열중 가장 사전순 가장 앞선 글자이므로, 뒤에서부터 최소값을 찾는 것과 동일합니다.  알고리즘 효율은 \(O(N)\)입니다.

 

첫번째 알고리즘입니다.

"""
    baekjoon #1464 - Reverse 3
        - by Aubrey Choi
        - created at 2022-08-18
"""
def next(s, i, j):
    mini = i;
    for k in range(i-1, j-1, -1):
        if s[k] < s[mini]: mini = k
    return s[:j]+ s[mini] + s[j:mini] + s[mini+1:], mini
s = input()
i, j = len(s)-1, 0
while i > j:
    s, i = next(s, i, j)
    j += 1
print(s)

 

두번째 알고리즘입니다.  훨씬 알고리즘이 간단하고 효율적인 것을 알 수 있습니다.

"""
    baekjoon #1464 - Reverse 3
        - by Aubrey Choi
        - created at 2022-08-18
"""
s = input()
s1 = s[0]
for i in range(1, len(s)):
    if s1[i-1] < s[i]: s1 = s[i]+s1
    else: s1 = s1+s[i]
print(s1[::-1])