Codeforces Round #530 (Div. 2) C. Postcard

문제링크 : https://codeforces.com/contest/1099/problem/C

<입력>

- '?'와 '*'이 포함된 문자열

- 만들고 싶은 문자열 길이

<출력>

- ?와 *의 기능을 이용해서 원하는 길이로 만들어진 문자열

- 불가능할 경우 Impossible

<풀이>

내가 알고리즘 문제를 풀 때 가장 어려워하는 문자열 가지고 놀기 문제이다.

먼저, '?'와 '*'의 기능을 살펴보자.

'?'는 앞에 있는 문자 1개를 지우거나 혹은 남겨둘 수 있다.

'*'는 앞에 있는 문자 1개를 지우거나 혹은 남겨둘 수 있고 추가로 원하는 개수만큼 복사할 수 있다.

주어진 문자열에서 기호의 기능을 사용해 만들 수 있는 많은 문자열 중 아무거나 하나만 출력해도 된다.

이 조건이 문제를 굉장히 쉬워지게 만들었다.

3가지 경우로 나눠서 문제를 풀 수 있다.

1. 만들고 싶은 문자열의 길이가 더 길 경우

2. 만들고 싶은 문자열의 길이가 더 짧을 경우

3. 만들고 싶은 문자열의 길이가 같을 경우

여기서 주의해야할 점이 있다. 3가지 경우 중 어떤 경우인지 상관없이 '?'와 '*'는 지워져야 한다.

따라서 처음부터 만들고 싶은 문자열의 길이와 주어진 문자열에서 '?','*'를 제외한 문자열의 길이를 비교해야 한다.

1의 경우는 '*'가 필요하다. '?'는 문자를 추가할 수 없기 때문이다. 그리고 '*'가 1개만 존재하면 첫 번째 '*'앞의 문자만 원하는 문자열의 길이가 될 때까지 계속해서 추가하고 나머지 기호들은 앞의 문자를 남기는 기능(앞의 문자에 영향을 끼치지 않고 혼자 사라짐)을 사용하면 쉽게 해결할 수 있다.

2의 경우는 '*'와 '?'는 문자를 최대 1개만 지울 수 있다. 따라서 앞에서부터 탐색하며 원하는 문자열의 길이가 될 때까지 기호를 만날때마다 1개씩 지워나가면 된다. 모든 기호가 앞의 문자를 지웠음에도 여전히 원하는 길이를 만들지 못했다면 해당 길이를 만들 수 없는 것이다. 즉, Impossible이다.

3. 만들고 싶은 문자열과 길이가 이미 같다면 그냥 기호들을 전부 제거하면 된다.

---

- 소스 코드 -

#include<iostream>
#include<string>
 
using namespace std;
 
int main(void) {
    char input[202];
    cin >> input;
    string result = "";
    int dest = 0;
    cin >> dest;
    int sig_num = 0;
 
    for (int i = 0; i < strlen(input); i++) {
        if (input[i] == '?'||input[i] == '*') {
            sig_num++;
        }
    }
    int char_num = strlen(input) - sig_num;
 
    for (int i = 0; i < strlen(input); i++) {
        if (dest > char_num) {
            if (input[i] != '?'&&input[i] != '*') {
                result += input[i];
            }
            else if (input[i] == '*') {
                int temp = result.size();
                for (int j = 0; j < dest - char_num; j++) {
                    result+=result.at(temp-1);
                }
                char_num = dest;
            }
        }
        else if (dest < char_num) {
            if (input[i] != '?'&&input[i] != '*') {
                result += input[i];
            }
            else{
                result.erase(result.end() - 1, result.end());
                char_num--;
            }
        }
        else {
            if (input[i] != '?'&&input[i] != '*') {
                result += input[i];
            }
        }
    }
    if (result.size() != dest) {
        cout << "Impossible" << endl;
    }
    else {
        cout << result << endl;
    }
}

---