https://www.acmicpc.net/problem/10453
문제 키워드에 애드혹이 있던데 잘은 모르겠습니다.
제가 이 로직으로 접근하기 위해 생각한것 자체가 애드혹이 될 수는 있겠네요!
1. ab 는 좋은 문자열이다.
2. 만약 문자열 [S]가 좋은 문자열이라면, 오른쪽과 왼쪽 끝에 각각 a와 b를 추가한 문자열 a[S]b 또한 좋은 문자열이다.
3. 만약 문자열 [S]와 [T]가 좋은 문자열이라면 이들을 붙여 쓴 [S][T] 또한 좋은 문자열이다.
좋은 문자열의 정의가 이렇게 나옵니다.
그리고 입력으로 좋은 문자열 A, B가 주어지고, A -> B의 최소 연산 횟수를 구해야합니다.
우선 위 정의를 보고 알 수 있는건 "두 문자열의 구성은 같다" 입니다.
ab = S는 좋은 문자열이며, aSb도 좋은 문자열입니다. 그리고 SS도 좋은 문자열입니다.
여기서 사용된 a과 b의 갯수는 같습니다.
그렇다면 생각해볼 예외는 "두 문자열의 길이가 다른 경우" 입니다.
두 문자열의 길이가 다르다면 당연히 A -> B가 성립하지 않겠죠.
문제의 로직은
a, b의 갯수가 둘다 동일하기 때문에 b의 위치를 각각 찾습니다.
그리고 b 위치의 차이를 더합니다.
b의 갯수도 당연히 똑같기 때문에 하나라도 문자열의 길이를 벗어나면 종료할 수 있습니다.
|
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
|
#include <iostream>
using namespace std;
string x, y;
int len1, len2;
void func() {
if (len1 != len2) {
cout << "-1\m";
return;
}
int ret = 0;
int idx1 = 0;
int idx2 = 0;
while (1) {
while (idx1 < len1 && x[idx1] == 'a') idx1++;
while (idx2 < len2 && y[idx2] == 'a') idx2++;
if (idx1 >= len1 || idx2 >= len2) break;
ret += abs(idx1++ - idx2++);
}
cout << ret << '\n';
}
void input() {
cin >> x >> y;
len1 = x.size();
len2 = y.size();
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
int tc;
cin >> tc;
while (tc--) {
input();
func();
}
return 0;
}
|
cs |
'algorithm > String' 카테고리의 다른 글
| boj 9081 단어 맞추기 (0) | 2021.12.15 |
|---|---|
| boj 10096 세 친구 (0) | 2021.01.29 |