[C++] 백준 1141번: 접두사

문제 링크

백준 1141번: 접두사

문제 요약

주어진 문자열들 중에 접두사 관계가 성립하지 않는 최대 부분 집합의 크기를 구해야한다.

접근 방법

문자열을 정렬합니다. 그리고 순서대로, 아래의 문자열들과 비교하면서 현재 문자열이 다른 문자열의 접두사가 될 수 있는지 확인합니다. 만약 그러한 경우가 있다면 해당 문자열은 집합에서 배제시키는 쪽이 유리합니다.

어떤 문자열이 접두사가 될 때, 해당 문자열을 집합에 포함시키면 하나 이상의 다른 문자열들은 반드시 집합에서 빠져야 합니다. 이러면 개수에서 손해를 보기 때문에, 접두사가 되는 문자열을 위에서부터 배제해주면 됩니다.

코드

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
	int n;
	cin >> n;

	vector<string> v(n);
	vector<bool> check(n, true);

	for (int i = 0; i < n; i++)
		cin >> v[i];

	sort(v.begin(), v.end());

	for (int i = 0; i < v.size(); i++)
	{
		for (int j = i + 1; j < v.size(); j++)
		{
			if (v[j].substr(0, v[i].size()) == v[i])
			{
				check[i] = false;
				break;
			}
		}
	}

	int ans = 0;
	for (auto i : check)
		if (i)
			ans++;

	cout << ans;
	return 0;
}