[BOJ 16719] ZOAC
- 문제풀이
문제
2018년 12월, 처음 시작하게 된 ZOAC의 오프닝을 맡은 성우는 누구보다 화려하게 ZOAC를 알리려 한다.
앞 글자부터 하나씩 보여주는 방식은 너무 식상하다고 생각한 성우는 문자열을 보여주는 새로운 규칙을 고안해냈다!
규칙은 이러하다. 아직 보여주지 않은 문자 중 추가했을 때의 문자열이 사전 순으로 가장 앞에 오도록 하는 문자를 보여주는 것이다.
예를 들어 ZOAC를 보여주고 싶다면, A → AC → OAC → ZOAC 순으로 보여주면 된다.
바쁜 성우를 위하여 이 규칙대로 출력해주는 프로그램을 작성하시오.
입력
첫 번째 줄에 알파벳 대문자로 구성된 문자열이 주어진다. 문자열의 길이는 최대 100자이다.
출력
규칙에 맞게 순서대로 문자열을 출력한다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 1sec | 256MB |
힌트
ZOAC는 한양대학교 ERICA 알고리즘 학회 ‘영과일’에서 주최하는 알고리즘 대회 Zero One Algorithm Contest 의 약자이다.
풀이
주어진 문자열에서 문자를 하나씩 선택하여, 선택된 문자들이 원래 순서를 유지하며 결합했을 때 사전 순으로 가장 앞서는 문자열을 차례대로 출력하는 문제다. 매 순간마다 사전 순으로 가장 앞서는 결과를 만들기 위해 그리디 알고리즘을 활용한다.
핵심 원리는 현재 탐색 범위 내에서 가장 작은 문자를 먼저 선택하는 것이다. 문자를 선택한 후에는 해당 문자의 오른쪽 구간을 먼저 탐색해야 한다. 기준 문자 뒤에 새로운 문자가 붙는 것이 기준 문자 앞에 새로운 문자가 붙는 것보다 사전 순으로 더 앞서기 때문이다. 그 후 왼쪽 구간을 탐색하여 나머지 문자들을 채워 나간다.
해결 과정은 다음과 같다:
- 현재 범위
[left, right)에서 아스키 코드 값이 가장 작은 문자를 찾는다. - 해당 문자를 방문 표시(
used[i] = true)하고, 현재까지 선택된 문자 중 사용된 문자들만 순서대로 출력한다. - 선택된 문자의 오른쪽 구간
(min_index + 1, right)에 대해 재귀적으로 탐색을 수행한다. - 오른쪽 탐색이 모두 완료되면 왼쪽 구간
(left, min_index)에 대해 재귀적으로 탐색을 수행한다.
문자열의 길이를 $L$이라고 할 때, 각 단계에서 최솟값을 찾는 데 $O(L)$이 소요되며 모든 문자를 한 번씩 방문하므로 전체 시간 복잡도는 다음과 같다:
\[O(L^2)\]문자열의 길이가 최대 100이므로 이 방식은 제한 시간 내에 충분히 수행 가능하다.
소스코드
Github Link : Source Code
참고 알고리즘 : 그리디 알고리즘