Codeforces Round #738 (Div. 2)-B. Mocha and Red and Blue

문제 설명

타일 $n$개가 일렬로 나란히 놓여있다. 그리고 이 타일은 빨간색 혹은 파란색으로 색칠할 수 있다.

이 타일중 몇개는 이미 색칠되어 있을 수도 있다. 그렇지 않은 타일은 빈칸으로 놓여있다. 우리가 해야할 일은 빈 타일을 무슨색으로 칠해야 할지 결정해야 하는것이다.

몇개의 인접한 타일 쌍은 같은 색으로 칠해져 있을 수 있고 불완전하다. 우리는 같은 색으로 칠해져 있는 인접한 두 타일의 쌍의 개수를 불완전성 이라고 한다.

예를 들어 "BRRRBBR"의 불완전성은 3이다. "BB"가 1번, "RR"이 2번 등장했기 때문이다.

우리의 목표는 불완전성이 최소가 되도록 빈 타일을 색칠하는 것이다.

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

각 테스트 케이스의 첫번째 줄에는 타일의 길이 정수 $n (1 \le n \le 100)$ 가 주어진다.

각 테스트 케이스의 두번째 줄에는 세문자 'B', 'R', '?'으로 이루어진 길이가 $n$인 문자열 $s$가 주어진다. 'B'는 파란색 타일, 'R'은 빨간색 타일 그리고 '?'은 빈 타일이다.

Output
각 테스트케이스마다 불완전성이 최소가 되게 하는 빈 타일에 색깔이 칠해진 결과인 'R'과 'B'로만 이루어진 문자열을 출력한다. 답이 여러개 있으면 아무거나 출력해도 된다.

Example
input
5
7
?R???BR
7
???R???
1
?
1
B
10
?R??RB??B?

output
BRRBRBR
BRBRBRB
B
B
BRRBRBBRBR

문제 접근

사용한 알고리즘: 문자열, 그리디 알고리즘
걸린 시간 : 00:07
상대적으로 B번에는 백준에서 비슷한 유형의 문제를 많이 풀어봐서 접근 방법은 쉽게 떠올랐다. 그런데 코드가 길어지면 디버깅할 때 애로사항이 조금 생기는데, 오렌지 코더의 코드를 보고나서 유저의 아름다운 코드에 반해버렸다. 진짜 코드보고 아름답다라고 잘 하지 않는데, 아래에 있는 코드는 오렌지 코더의 코드를 보고 내 것으로 만들기 위해서 나름대로 스스로 적어본 코드이다. 고수들의 코드를 보는 것도 업솔빙의 하나의 중요한 과정이라는 사실을 알게됐다.

문제를 푸는 방식은 간단한 그리디 알고리즘이다. 인접해 있는 두 타일이 같은 색으로 칠하면 안되기 때문에 만약 한 타일이 파란색으로 칠해져 있다면 다음 타일은 빨간색, 그 다음 타일은 파란색순으로 이미 칠해져 있는 타일을 만날 때 까지 계속 번갈아가면서 타일을 칠해 나가면 된다. 이미 칠해져 있는 타일을 만날 때 이미 칠해져 있는 타일과 색깔이 같아도 상관 없다. 이 타일을 다른 타일로 칠하면 어짜피 이미 불완전성이 1증가하기 때문이다.

그나마 생각할점은 "????B"와 같이 빈 타일로 칠해지다가 도중에 색깔이 칠해져 있는 타일인 경우다. 이 경우는 2가지 경우로 나눌 수 있다.

1. 이미 칠해진 타일 앞에 있는 빈 타일의 개수가 짝수일때: 맨 앞에 있는 타일을 이미 칠해진 타일과 같은 색깔로 칠하고 계속 번갈아 색칠하면 된다.
2. 이미 칠해진 타일 앞에 있는 빈 타일의 개수가 홀수일때: 맨 앞에 있는 타일을 이미 칠해진 타일과 다른 색깔로 칠하고 계속 번갈아 색칠하면 된다.

왜 이래야 하는지는 몇번 직접 예시를 만들어봐서 테스트 해보면 답이 나올 것이다.

오렌지 코더에서 배운점은 다음과 같다.

1. 우리가 짝수 홀수를 판별할 때 쓰는 $n ; mod ; 2 == 0$ 를 (n & 1)로 더 깔끔하게 쓸 수 있다.
2. 2가지 문자중 하나와 다른 문자를 선택 할 때 그 문자를 더하고
   현재 문자를 빼면 현재 문자와 다른 문자가 나온다.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0);
    int T; cin >> T;
    while(T--){
        int n; cin >> n;
        string s; cin >> s;
        char cur = 'R';
        for(int i = 0; i < n; i++){
            if(s[i] != '?'){
                cur = (i & 1) ? 'R' + 'B' - s[i] : s[i];
                break;
            }
        }

        for(int i = 0; i < n; i++){
            if(s[i] == '?') s[i] = cur;
            cur = 'R' + 'B' - s[i];
        }
        cout << s << "\n";
    }
    return 0;
}