취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 28140번 문제인 빨강~ 빨강~ 파랑! 파랑! 달콤한 솜사탕!이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/28140 

주어진 문자열의 각 i번째 문자에 대하여 i 이상의 인덱스에서 등장하는 첫 번째 'B'는 몇 번째 인덱스인지, 'R'은 몇 번째 인덱스인지를 각각 저장해둔 배열을 만든다면 그리디한 알고리즘을 이용해 문제를 간단히 해결할 수 있다. 구체적으로, [l,r] 구간이 주어질 때 l부터 살폈을 때 가장 먼저 나오는 'R'의 인덱스 r1, r1+1부터 살폈을 때 가장 먼저 나오는 'R'의 인덱스 r2, r2+1부터 살폈을 때 가장 먼저 나오는 'B'의 인덱스 b1, b1+1부터 살폈을 때 가장 먼저 나오는 'B'의 인덱스 b2를 구했을 때 b2가 [l,r]에 속하는지를 살피는 것으로 문제를 해결할 수 있게 된다. 이 과정에서 그 뒤로 'B' 또는 'R'이 등장하지 않는 경우에 대한 예외처리를 적절히 해야 함에 유의하자.

위의 과정을 위한 배열은 문자열을 거꾸로 한 문자씩 살펴나가는 것으로 쉽게 구할 수 있다. 글쓴이는 disjoint set을 이용한 방법으로 해당 배열을 구하였다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N, Q;
int arrR[1000004], arrB[1000004];

int findR(int i) {
	if (arrR[i] == i) return i;
	else return arrR[i] = findR(arrR[i]);
}

int findB(int i) {
	if (arrB[i] == i) return i;
	else return arrB[i] = findB(arrB[i]);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> Q;
	for (int i = 0; i < N; i++) {
		char c; cin >> c;
		if (c != 'R') arrR[i] = i + 1;
		else arrR[i] = i;
		if (c != 'B') arrB[i] = i + 1;
		else arrB[i] = i;
	}
	for (int i = 0; i < 4; i++) arrR[N + i] = arrB[N + i] = N + i;

	while (Q--) {
		int L, R; cin >> L >> R;
		int ans1 = findR(L);
		int ans2 = findR(ans1 + 1);
		int ans3 = findB(ans2 + 1);
		int ans4 = findB(ans3 + 1);
		if (ans4 > R) cout << -1 << '\n';
		else cout << ans1 << ' ' << ans2 << ' ' << ans3 << ' ' << ans4 << '\n';
	}
}