취미로 코딩하기

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

이번에 볼 문제는 백준 24993번 문제인 KIARA is a Recursive Acronym이다.
문제는 아래 링크를 확인하자.

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

Acronym(두문자어)란 주어진 단어열의 첫글자를 따 이어붙여 만든 단어를 의미한다.

문제에서 주어진 Recursive Acronym이란, 원래의 단어열에 있던 단어가 Acronym이기도 한 경우의 acronym을 의미한다.

이 문제에서 단어열을 구성할 때 같은 단어를 여러 번 사용하는 것도 가능하므로, 알파벳별로 각 알파벳으로 시작하는 단어가 있는지를 먼저 조사하고, 각 단어마다 그 단어를 구성하는 알파벳으로 시작하는 단어가 있는지를 앞서 조사한 것을 이용해 빠르게 알아내는 것으로 문제를 해결할 수 있다.

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

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

int headletter[128];
string s[1000000];

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

	int N; cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> s[i];
		headletter[s[i][0]] = 1;
	}

	bool ans = 0;

	for (int i = 0; i < N; i++) {
		bool chk = 1;
		for (auto l : s[i]) {
			if (headletter[l] == 0) chk = 0;
		}

		if (chk) ans = 1;
	}

	if (ans) cout << 'Y';
	else cout << 'N';
}