Problem E 풀이 (C++)

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

모든 문자열을 합친다면 문자열의 길이가 너무 길어 계산 불가.

그렇기 때문에 직접 계산하지 않고 각 변수의 문자열의 "haha" 포함 개수와

문자열의 앞쪽 최대 3개와 뒤쪽 최대 3개 문자를 데이터로 사용하여 계산한다.

( 최대 3개인 이유는 아래에 나와있다. )

계산을 편하게 하기 위해 우리가 계산하고자 하는 데이터의 구조를 새로 정의해서 사용.

각 변수마다 해당 데이터를 가진다.

1
2
3
4
5
6
class hstring {
public:
    long long hahanum = 0;
    string front = "";
    string back = "";
};
cs

":=" 연산에서는

단지 문자열을 대입하는 명령이다.

haha를 검색하여 포함된 개수를 찾고

앞의 최대 3개 문자 ( 문자열의 길이가 3보다 작으면 개수가 문자열의 길이만큼. )

뒤의 최대 3개 문자 ( 앞의 조건과 같다. )

를 구하여 hstring 데이터를 생성하여 map<string, hstring>을 통해 저장한다.

이 map에서 key는 변수 이름이고 value는 hstring 데이터이다.


"=" 연산에서는

변수 2개 var1, var2의 string을 합치는 과정이다.

이경우 "haha"의 개수는 기본적으로 2개의 데이터를 합친다.

하지만 이 경우 한 가지 생각해야 하는 과정이 있는데

두 문자열이 붙는 부분에서 "haha"가 생길 수 있다는 점이다.

"haha"가 최대로 생기는 경우는 "~~hah" 와 "aha~~" 문자열이 붙는 경우다.

그래서 앞의 3개 뒤의 3개 문자열만 생각한다. 이보다 더 길어지면 어차피 기본 haha 개수에 포함된다.

그래서 var1의 뒤 문자열과 var2의 앞 문자열을 합친 문자열에서 haha를 검색하여 개수를 더한다.

그리고 합쳐진 문자열의 앞 문자는 기본적으로 var1의 앞 문자이고 뒤 문자는 var2의 뒤 문자이다.

하지만 이 문자의 개수가 3개 미만인 경우에는 합쳐진 문자열을 생각해서 갱신 해 줘야한다.

var1의 앞 문자가 3개 미만이면 var2의 앞 문자에서 3개가 될 때까지 붙인다. ( 이때 var2의 앞 문자에서도 개수가 부족할 수 있다. )

뒤 문자도 마찬가지로 진행하여

"haha"의 개수, 앞의 문자열, 뒤의 문자열 데이터를 가진 hstring 데이터를 생성하여 해당 변수에 해당하는 map의 저장 공간에 저장한다.

이 방식으로 끝까지 갔을 때 map에서 마지막 변수에 해당하는 데이터를 가져오면 답을 출력할 수 있다.


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
93
94
95
96
97
98
99
100
101
102
103
104
#include <iostream>
#include <map>
 
using namespace std;
 
class hstring {
public:
    long long hahanum = 0;
    string front = "";
    string back = "";
};
 
// get the number of "haha" included in string.
int getHahaNum(string str) {
    
    int result = 0;
    
    while (true) {
        int idx = str.find("haha");
        if (0 <= idx && idx < str.length()) {
            result++;
            str = str.substr(str.find("haha") + 2);
        }
        else
            break;
    }
 
    return result;
}
 
int main() {
 
    int t;
    cin >> t;
 
    while (t--) {
 
        int n;
        cin >> n;
 
        map<string, hstring> m;
        string var;
 
        while (n--) {
 
            string oper1, rv1, oper2, rv2;
 
            cin >> var >> oper1 >> rv1;
 
            hstring data;
 
            if (oper1 == ":=") {
                
                data.hahanum = getHahaNum(rv1);
 
                if (rv1.length() >= 3) {
                    for (int i = 0; i < 3; i++) {
                        data.front += rv1[i];
                        data.back += rv1[rv1.length() - 3 + i];
                    }
                }
                else {
                    data.front = data.back = rv1;
                }
 
            }
            else {
 
                cin >> oper2 >> rv2;
 
                hstring rd1 = m[rv1], rd2 = m[rv2];
 
                data.hahanum = rd1.hahanum + rd2.hahanum + getHahaNum(rd1.back + rd2.front);
                data.front = rd1.front;
                data.back = rd2.back;
 
                if (data.front.length() < 3) {
                    for (int i = 0; i < rd2.front.length(); i++) {
                        data.front += rd2.front[i];
                        if (data.front.length() == 3)
                            break;
                    }
                }
 
                if (data.back.length() < 3) {
                    string changed = "";
                    for (int i = rd1.back.length() - (3 - rd2.back.length()); i < rd1.back.length(); i++) {
                        if (i >= 0)
                            changed += rd1.back[i];
                    }
                    changed += data.back;
                    data.back = changed;
                }
 
            }
 
            m[var] = data;
        }
 
        cout << m[var].hahanum << endl;
    }
 
    return 0;
}
cs

댓글

댓글 쓰기