[BOJ/Gold 4] 백준 1464 뒤집기 3(C++)

문제 링크

https://www.acmicpc.net/problem/1464

1464번: 뒤집기 3

 

 

문제

세준이는 어떤 문자열 S를 뒤집으려고 한다. 문자열을 뒤집는 방법은 문자열의 길이를 N이라고 하자. i만큼을 뒤집는다는 소리는 그 문자열의 처음부터 정확하게 i개의 문자를 역순으로 뒤집는 것이다. 세준이는 1부터 N까지 수를 차례대로 생각한다. 그리고, 뒤집을지 안 뒤집을지 선택할 수 있다.

예를 들어, S="BCDAF" 이고, 세준이가 길이 1만큼을 뒤집지 않고, 길이 2만큼도 뒤집지 않고 세준이가 길이 3만큼을 뒤집는다고 하면 문자열은 DCBAF가 된다. 다시 여기서 4만큼 뒤집으면 ABCDF가 된다. 그리고, 마지막으로 길이를 5만큼 뒤집지 않으면 주어진 문자열 S를 사전순으로 가장 앞서게 만들 수 있다.

문자열 S가 주어졌을 때, 위와같은 뒤집기 방법으로 만들 수 있는 문자열 중 사전순으로 제일 앞서는 것을 출력하시오.

입력

첫째 줄에 문자열 S가 주어진다. 문자열의 길이는 최대 50이다. 알파벳 대문자만 들어온다.

출력

첫째 줄에 사전순으로 가장 앞서는 정답을 출력한다.

예제 입력 1

BCDAF

예제 출력 1

ABCDF

예제 입력 2

ABBA

예제 출력 2

AABB

예제 입력 3

ACAB

예제 출력 3

AACB

알고리즘 분류

• 그리디 알고리즘
• 자료 구조

풀이

가능한 한 사전순으로 앞서는 문자열을 찾아야 하기 때문에 그리디하게 접근할 필요가 있다.

덱을 이용하여 문자열의 첫 번째 문자부터 덱의 앞에 push할 지, 뒤에 push할 지를 결정한다.

i번째 문자를 앞에 push하는 것은 i번째 문자까지 문자열을 뒤집었다는 뜻이며, 뒤에 push했다는 것은 i번째 문자까지 문자열을 뒤집지 않았다는 뜻이 된다.

먼저 첫 번째 문자는 그냥 push한다.

그리고 두 번째 문자부터 덱의 front, back과 비교하여, 먼저 front보다도 사전 순으로 앞서는 문자라면 덱의 앞에 push해주고, back보다도 사전 순으로 뒤에 있는 문자라면 덱의 뒤에 push해준다. 어느 것에도 해당되지 않는다면 덱의 뒤에 push해준다.

마지막으로 덱의 front에서부터 문자를 하나씩 출력하고 pop_front해준다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <deque>
#include <algorithm>
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
string S;
deque<char> DQ;

void input() {
    cin >> S;
}

void settings() {
    for (int i = 0; i < S.size(); i++) {
        char Now = S[i];
        if (DQ.empty()) {
            DQ.push_back(Now);
        }
        else if (DQ.back() <= Now) {
            DQ.push_back(Now);
        }
        else if (DQ.front() >= Now) {
            DQ.push_front(Now);
        }
        else {
            DQ.push_back(Now);
        }
    }
}

void find_Answer() {
    while (!DQ.empty()) {
        cout << DQ.front();
        DQ.pop_front();
    };
    cout << "\n";
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}