ZOAC(백준 16719번)

💡 **Check Point !

( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?✓

---

난이도 체감

1. 최상

2. 상

3. 중✓

4. 하

---

이해도

1. 완벽히 이해✓

2. 다소 헷갈리는 부분들이 있음

3. 이해 못함

문제

2018년 12월, 처음 시작하게 된 ZOAC의 오프닝을 맡은 성우는 누구보다 화려하게 ZOAC를 알리려 한다.

앞 글자부터 하나씩 보여주는 방식은 너무 식상하다고 생각한 성우는 문자열을 보여주는 새로운 규칙을 고안해냈다!

규칙은 이러하다. 아직 보여주지 않은 문자 중 추가했을 때의 문자열이 사전 순으로 가장 앞에 오도록 하는 문자를 보여주는 것이다.

예를 들어 ZOAC를 보여주고 싶다면, A → AC → OAC → ZOAC 순으로 보여주면 된다.

바쁜 성우를 위하여 이 규칙대로 출력해주는 프로그램을 작성하시오.

나의 풀이(정답 참고)

def solve(start,S,show):
    if not S:
        return
    min_ch=min(S)
    idx=S.index(min_ch)
    show[start+idx]=min_ch
    print(''.join(show))
    solve(start+idx+1,S[idx+1:],show)
    solve(start,S[:idx],show)

S=input()
show=['']*len(S)

solve(0,S,show)

• 위 문제는 재귀함수로 풀었다. 아직 재귀함수를 활용하는 것에 많이 익숙하지는 않은 것 같다.
• 또한 문자열이 최대 100이기 때문에, min, index와 같은 함수를 써도 괜찮았다.(시간 복잡도 생각을 잘 못하는 것 같다, 조금 더 생각하자)
• 해당 문자열에서 가장 아스키코드 값이 작은, 즉 사전 배열에서 우선순위가 되는 문자를 찾고, 그 문자를 추가한다. 그 후 재귀함수에, 그 이후 문자열을 먼저 넣어준다.(사전에서 그 뒤에 문자가 우선 순위가 있기 때문이다.
• 그 후, 앞의 문자열에 대해 solve함수를 처리해준다.