취미로 코딩하기

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

이번에 볼 문제는 백준 21375번 문제인 Konamikoden이다.
문제는 아래 링크를 확인하자.

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

주어진 문자열에서 "UUNNVHVHBA"를 subsequence로 갖는 가장 짧은 substring의 길이를 찾는 문제이다. (그러한 substring이 있음이 보장된다.)

각 문자마다 다음으로 'U', 'N', 'V', 'H', 'B', 'A'가 등장하는 위치를 저장한 배열을 미리 만들어두면 각 문자마다 어느 인덱스까지 포함해야 "UUNNVHVHBA"를 부분문자열로 포함하게 되는지를 $O(1)$의 시간(9~10번의 인덱스 이동)에 계산할 수 있다. 각 문자별 배열을 계산할 때, 같은 인덱스에 중복해서 저장해야 하는 일이 없도록 구현하면 배열 하나당 $O(N)$의 시간복잡도로 구할 수 있다.

각 문자로부터 해당 문자열을 만들기 위해 포함해야하는 길이를 각각 구해 문제를 해결하자.

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

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

int K;
string A;
int U[200001], N[200001], V[200001], H[200001], B[200001], AA[200001];
int ans = 1000000007;

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

	cin >> A;
	K = A.length();
	for (int i = 0; i < K; i++) {
		if (A[i] == 'U') {
			for (int k = i - 1; k > -1 && !U[k]; k--) U[k] = i;
		}
		else if (A[i] == 'N') {
			for (int k = i - 1; k > -1 && !N[k]; k--) N[k] = i;
		}
		else if (A[i] == 'V') {
			for (int k = i - 1; k > -1 && !V[k]; k--) V[k] = i;
		}
		else if (A[i] == 'H') {
			for (int k = i - 1; k > -1 && !H[k]; k--) H[k] = i;
		}
		else if (A[i] == 'B') {
			for (int k = i - 1; k > -1 && !B[k]; k--) B[k] = i;
		}
		else if (A[i] == 'A') {
			for (int k = i - 1; k > -1 && !AA[k]; k--) AA[k] = i;
		}
	}

	for (int i = 0; i <= K; i++) {
		if (!U[i]) U[i] = K;
	}
	for (int i = 0; i <= K; i++) {
		if (!N[i]) N[i] = K;
	}
	for (int i = 0; i <= K; i++) {
		if (!V[i]) V[i] = K;
	}
	for (int i = 0; i <= K; i++) {
		if (!H[i]) H[i] = K;
	}
	for (int i = 0; i <= K; i++) {
		if (!B[i]) B[i] = K;
	}
	for (int i = 0; i <= K; i++) {
		if (!AA[i]) AA[i] = K;
	}

	for (int i = 0; i < K; i++) {
		if (A[i] != 'U') continue;
		int ii = AA[B[H[V[H[V[N[N[U[i]]]]]]]]];
		if (ii < K) ans = min(ans, ii - i + 1);
	}

	cout << ans - 10;
}