BOJ 16719 : ZOAC

풀이 요약

이분탐색

풀이 상세

1. 먼저 문자 범위를 지정하여 그 반경의 최소의 문자를 구한다.

2. 출력한다.

3. 사전순으로 정의하기 위해 최소의 문자 인덱스 +1, 이전 반경의 마지막 범위를 탐색한다.

4. 2의 작업이 끝나면 이번엔 이전 반경의 시작 범위, 최소의 문자 인덱스 - 1 범위를 탐색한다.

5. 2~4의 과정을 모든 작업이 끝날 때 까지 반복한다.

배운점

• 매 재귀마다 찾아야 하는 최소의 문자는 찾았으나 이를 어떻게 출력할지를 고민했다.
• 파라미터를 더 추가하거나, 비트마스킹을 통해서도 가능할거라고 생각했으나 되지 않았다. 그냥 방문처리를 한 후, 문자열 순서대로 출력하도록 했다.

#include <iostream>
using namespace std;
string str;
bool visited[100];
void solve(int st, int ed) {
    if(st>ed) return;

    int minIdx = ed+1;
    char minChar = 'Z'+1;
    for(int i=st; i<=ed; i++) {
        if(minChar > str[i]) {
            minChar = str[i];
            minIdx = i;
        }
    }
    visited[minIdx] = true;
    string tmp = "";
    for(int i=0; i<str.length(); i++)
        if(visited[i]) tmp += str[i];

    cout << tmp << "\n";
    solve(minIdx+1, ed);
    solve(st,minIdx-1);
}
int main() {
    cin >> str;
    solve(0, str.length()-1);
}