Educational Codeforces Round 113 (Rated for Div. 2)-A. Balanced Substring

문제 설명

알파벳 'a'와 'b'로 이루어지고 $n$개의 문자로 이루어진 문자열 $s$가 주어진다. 이 문자열의 index는 $1$ 번부터 $n$번까지로 나타낸다.

$s[l;r]$은 index $l$ 부터 $r$까지 string $s$의 부분 문자열이다. 이때 index $r$과 $s$모두 포함한다.

어떤 문자열이 문자 'a'의 개수와 문자 'b'의 개수가 같으면 그 문자열은 "균형잡혔다"고 말한다. 예를들어 문자열 "baba"와 "aabbab"는 균형잡혔지만 문자열 "aaab"와 "b"는 균형잡히지 않았다.

한 문자열에서 균형잡힌 부분 문자열 $s[l:r]$ 을 찾는 것이 우리의 목표이다. 균형잡힌 문자열을 찾은 경우 $l$과 $r(1 \le l \le r \le n)$을 출력하고, 찾지 못한 경우 $-1 -1$을 출력한다.

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

각 테스트케이스의 첫번째 줄에는 문자열의 개수 $n$이 주어진다. $(1 \le n \le 50)$

각 테스트케이스의 두번째 줄에는 $n$자리로 이루어진 문자열이 주어진다. 문자열에 포함된 각 문자는 'a'와 'b'로만 이루어져 있다.

Output
각 테스트 케이스마다 두 정수를 출력한다. 균형잡힌 문자열 $s[l;r]$이 존재하면 $l r(1 \le l \le r \le n)$을 출력하고, 그렇지 않으면 $-1 -1$을 출력한다.

Example
input
4
1
a
6
abbaba
6
abbaba
9
babbabbaa

output
-1 -1
1 6
3 6
2 5

문제 접근

사용한 알고리즘: 구현
걸린 시간 : 00:08
우리가 찾는 것이 부분 문자열이기 때문에 문제가 어려워 보이지만 그냥 문자열을 찾는 것보다 생각보다 쉬운 문제이다.
결국 a와 b의 개수가 같은 부분문자열만 찾으면 되기 때문에 'ab'나 'ba'만 찾으면 되는 간단한 문제이다.
첫번째 index에 위치한 문자를 start라고 하고, 그 문자와 다른 문자가 나온 순간을 단순히 저장해서 그 전 index와 저장한 index를 출력하면 된다. 이때 b가 -1인 경우는 첫번째 문자와 다른 문자가 나오지 않았다는 뜻이므로 -1 -1을 출력한다.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        string str; cin >> str;
        char start = str[0];
        int a = -1, b = -1;
        for(int i = 0; i < n; i++){
            if(str[i] != start){
                b = i + 1;
                break;
            }
            a = i + 1;
        }
        cout << (b == -1 ? -1 : a) << " " << b << "\n";
    }
    return 0;
}