Problem E 풀이 (C++)

 문제 링크 : https://codeforces.com/contest/1560/problem/E

문자열 t에서 마지막 문자가 마지막으로 지워진 문자이다.

그리고 마지막에 연속으로 붙어있는 개수가 처음 문자열에 포함되어 있는 마지막으로 지워진 문자의 개수이다.

문자열 t의 마지막 문자부터 처음 문자까지 차례대로 확인하면서

기존에 확인된 문자들 이외의 처음 나오는 문자는 바로 이전에 지워진 문자라는 것을 알 수 있다.

이 과정을 통해서 문자열을 구성하고 있는 문자들과 지워진 문자의 순서를 알 수 있다.

또한 t를 구성하고 있는 각 문자들의 개수를 세어 처음 문자열에 포함되어 있는 각 문자의 개수를 알 수 있다.

지워진 문자의 순서를 안다면 각 문자마다 문자열 t에 몇 번 붙여졌는지 횟수를 알 수 있고

이 횟수로 문자열 t에 포함된 문자의 개수를 나누면 초기 문자열에 포함된 각 문자의 개수를 알 수 있다.

( 이때 각 문자마다 이 나누기 계산을 진행했을 때 나머지가 0이 아니라면 -1을 출력한다. )

그리고 이 정보를 이용해 초기 문자열의 길이를 알 수 있고

해당 길이만큼 문자열 t에서 확인했을 때 이전에 계산했던 각 문자의 초기 문자열에 있는 개수와 전부 맞는다면

문자열 t에서의 초기 문자열이 될 수 있다는 의미이고, 개수가 맞지 않다면 -1을 출력한다.


초기 문자열까지 구했다면, 이 초기 문자열과 이전에 구했던 지워진 순서를 이용하여

문자열 t를 만드는 과정을 그대로 진행하여 입력받은 문자열 t와 일치한다면 답을 출력하고 일치하지 않는다면 -1을 출력한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include <map>
 
using namespace std;
 
int main() {
 
    int T;
    cin >> T;
 
    while (T--) {
 
        string t;
        cin >> t;
 
        string s = "";
        string delorder = "";
 
        map<char, int> m;
 
        for (int i = t.length() - 1; i >= 0; i--) {
 
            if (m.count(t[i]) == 0)
                delorder = t[i] + delorder;
                
            m[t[i]]++;
        }
 
        int slength = 0;
 
        bool isFalse = false;
 
        for (int i = 0; i < delorder.length(); i++) {
            if (m[delorder[i]] % (i + 1) != 0) {
                isFalse = true;
                break;
            }
            else {
                m[delorder[i]] /= (i + 1);
                slength += m[delorder[i]];
            }
        }
 
        if (isFalse == true) {
            cout << -1 << endl;
            continue;
        }
 
 
        for (int i = 0; i < slength; i++) {
            s += t[i];
            m[t[i]]--;
        }
 
        for (auto a : m) {
            if (a.second != 0) {
                isFalse = true;
                break;
            }
        }
 
        if (isFalse == true) {
            cout << -1 << endl;
            continue;
        }
 
        string tt = "";
        string ss = s;
 
        for (int i = 0; i < delorder.length(); i++) {
 
            tt += ss;
 
            char dela = delorder[i];
 
            string nss = "";
            for (int j = 0; j < ss.length(); j++)
                if (ss[j] != dela)
                    nss += ss[j];
 
            ss = nss;
        }
 
        if (t == tt) {
            cout << s << " " << delorder << endl;
        }
        else
            cout << -1 << endl;
    }
 
    return 0;
}
cs

댓글

댓글 쓰기