백준 1464 - 뒤집기 3

문제 설명

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

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

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 문자열이 주어졌을 때, 문자열을 적절히 뒤집어 사전순으로 가장 빠른 문자열을 찾아야 한다.

문자열을 뒤집는 규칙은 가장 앞에서부터 i번째까지 뒤집는 것이다.

이때, i는 1부터 문자열의 길이만큼 순차적으로 진행된다.

 

해당 문제를 풀기 위해서는 두 가지 개념이 필요하다.

• i번째 문자열까지 뒤집어온 문자열은 항상 최적해를 유지한다.
• 최적해를 구하기 위해서는 이전까지의 문자열을 한번 뒤집고 다시 한 번 뒤집어야 한다.
  • (i-1번째까지의 답을 뒤집고 i번째까지를 다시 뒤집는 것을 의미)

 

첫 번째 개념은 간단하다.

항상 최적해를 유지하면 문자열의 길이만큼 진행하면 답을 얻을 수 있음과 동시에 두 번째 개념을 통해 답을 쉽게 구할 수  있다.

두 번째 개념은 예를 들어 이해하는 것이 편하다.

예를 들어, "CDABA"라는 문자열이 주어졌다고 가정해 보자.

우선, 1부터 진행해보면 "C"가 될 것이다.

이는 뒤집어도 "C"이기 때문에 사실 의미가 없다.

그럼, "CDA"를 생각해 보자.

"CDA"는 사전순으로 가장 빠른 문자열이 아니다.

즉, 이 부분 문자열은 뒤집어야 한다.

이때, 그냥 뒤집는다면 "ADC"가 된다. 하지만, 이 역시도 사전순으로 가장 빠른 문자열이 아니다.

사전순으로 가장 빠른 문자열은 "ACD"가 되어야 한다.

즉, A를 발견하기 전까지인 문자열 "CD"는 사전순으로 가장 빠른 문자열을 유지하고 있을 테니 이를 한 번 뒤집고 A를 포함한 문자열을 다시 뒤집는다면 사전순으로 가장 빠른 문자열을 얻을 수 있다.

"CD" → "DC" → "DCA" → "ACD"

이런 식으로 진행 될 것이다.

이를 코드로 간단하게 나타내면 다음과 같다.

if (str[i - 1] < str[i])
{
    reverse(str.begin(), str.begin() + i - 1);
    reverse(str.begin(), str.begin() + i);
}

 

이 역시 정답이 될 수 있지만, reverse연산이 불필요하게 많이 진행될 수 있다.

이를 해결하기 위해, 실제 문자열을 뒤집는 게 아니라 새로운 문자열을 만든다고 생각해 보자.

새로운 문자열을 만들기 위해 str[i]번째 문자를 추가할 것인데 이를 제일 앞에 추가할 것인지 제일 뒤에 추가할 것인지를 선택하며 진행하는 것이다.

만약, "CD"인 상태에서 'A'를 추가한다고 하면 'C'앞에 붙어야 하기 때문에 앞에 추가해 주고 그렇지 않다면 뒤에 추가하는 것이다.

정리하자면, 새로 만드는 문자열의 제일 앞 문자를 보고 추가할 문자를 어디에 추가할지 결정하는 것이다.

string ans;
ans += str[0];

for (int i = 1; i < N; i++)
{
    if (ans[0] < str[i])
    {
        ans = ans + str[i];
    }
    else
    {
        ans = str[i] + ans;
    }
}

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

string str;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout.precision(4);

    cin >> str;
    const int N = str.length();

    string ans;
    ans += str[0];

    for (int i = 1; i < N; i++)
    {
        if (ans[0] < str[i])
        {
            ans = ans + str[i];
        }
        else
        {
            ans = str[i] + ans;
        }
    }

    cout << ans;

    return 0;
}

---