Educational Codeforces Round 116 - A. AB Balance

문제 설명

문자 a와 b로만 이루어져 있는 길이가 $n$인 문자열 $s$가 주어진다.

$AB(s)$를 $s$의 substring 인 ab의 출현 횟수라고 하고, $BA(s)$를 $s$의 substring 인 ba의 출현 횟수라고 하자.

한 단계에서 우리는 index $i$를 선택하고 $s_i$를 문자 a나 b로 바꿀 수 있다.

$AB(s) = BA(s)$ 가 되기 위해서 필요한 최소 연산은 무엇일까?

Input
첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t (1 \le t \le 1000)$ 이 주어진다.

각 테스트케이스의 첫번째 줄에는 문자열 $s (1 \le |s| \le 100)$ 가 주어진다. 이때 $|s|$ 는 문자열 $s$의 길이를 의미하고 이 문자열은 a와 b로만 이루어져 있다.

Output
각 테스트 케이스마다 최소 단계를 거쳐서 나온 $AB(s) = BA(s)$ 를 만족하는 문자열 $s$를 출력한다.

만약 답이 여러개 있다면 아무거나 출력한다.

Example
input
4
b
aabbbabaa
abbb
abbaab

output
b
aabbbabaa
bbbb
abbaaa

문제 접근

사용한 알고리즘: 문자열
걸린 시간 : 00:01
처음 이 문제를 접했을때 10분이 걸려도 못풀어가지고 아 이번 contest도 망했구나라고 생각했는데, 생각보다 B번 문제를 30분안에 풀어서 계속 시도해본 결과 풀었던 문제이다.

대회때와 해설의 차이가 좀 너무 많이 나서 괴리감이 든 문제이기도 하다. codeforces A번 문제에 나오는 ab string문제들은 결국 a와 b가 바뀌는 부분을 잘 생각하면 아이디어가 나온다고 생각해서 그곳을 집중적으로 봤다. 내가 푼 방법은 처음 ab or ba가 나오면 그 다음에 반드시 ab or ba가 나와야 한다는 것을 이용했다. 즉 처음에 ab가 나오면 그 다음에 ba가 나와야 하고, 처음에 ba가 나오면 그 다음에는 ab가 나와야 한다. 그래서 $s[i] != s[i - 1]$ 인 지점이 짝수번 나오면 문자열을 바꿀 필요 없고, 홀수번 나오면 한 문자만 바꾸면 된다고 해서 풀었다.

하지만 해설을 보니 그냥 처음과 끝이 같으면 무조건 $AB(s) = BA(s)$ 이고 그렇지 않으면 그냥 처음과 끝을 같게 만들어주는 연산 1회만 하면 답이 된다는 것을 알았다. 이것도 몇번 테스트 케이스를 생각해보면 알 수 있다는 점에서 좀 아쉬운 문제였다. 진짜 이제는 ab string으로 나올 수 있는 유형은 다 나온줄 알았는데, 더 있다는 것에 놀란 문제였다.

정답 코드

#include <iostream>
#include <string>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        string s; cin >> s;
        if(s[0] != s[s.size() - 1]) s[0] = s[s.size() - 1];
        cout << s << "\n";
    }
    return 0;
}