백준 1141 - 접두사

문제 설명

접두사X 집합이란 집합의 어떤 한 단어가, 다른 단어의 접두어가 되지 않는 집합이다. 예를 들어, {hello}, {hello, goodbye, giant, hi}, 비어있는 집합은 모두 접두사X 집합이다. 하지만, {hello, hell}, {giant, gig, g}는 접두사X 집합이 아니다.

단어 N개로 이루어진 집합이 주어질 때, 접두사X 집합인 부분집합의 최대 크기를 출력하시오.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 문자열을 적절히 선택하여 서로 접두사가 되지 않는 문자열 집합의 최대 크기를 구하는 것이다.

 

해당 문제는 모든 부분 집합을 검사한다면 시간초과가 발생한다.

이를 해결하기 위해 정렬과 dp를 사용하면 된다.

 

우선, 정렬을 통해 사전순, 길이순으로 정렬한다.

정렬을 하는 이유는 현재 문자열의 접두사가 되는 문자열과 비교하지 않기 위해서이다.

예를 들어, {h, hi, hello}와 같은 집합이 있을 때, 집합을 정렬하면 {h, hello, hi}이 된다.

hello를 검사할 때, 자신보다 사전순이 빠르며 길이가 짧은 h는 비교하지 않아도 된다.

h에서 자신이 접두사가 되는 문자열들을 이미 파악했기 때문이다.

 

그리고 dp를 통해 자신이 접두사가 되지 않는 문자열에 최대 집합의 수를 갱신하면 된다.

우선, 모든 문자열을 자기 자신만 포함된 크기가 1인 집합을 기본적으로 만들 수 있다.

이후, 자신이 다른 문자열과 비교하여 접두사가 되지 않는다면 자신의 최대 집합 개수에 1을 더해 해당 문자열에 기록하면 된다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int N;

bool CheckPre(string& pre, string& target)
{
    bool flag = true;
    for (int i = 0; i < pre.length(); i++)
    {
        if (pre[i] != target[i])
        {
            flag = false;
            break;
        }
    }

    return flag;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;

    cin >> N;

    vector<string> words(N);
    vector<int> dp(N, 1);

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

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

    int ans = 1;
    for (int i = 0; i < N; i++)
    {
        for (int j = i+1; j < N; j++)
        {
            if (!CheckPre(words[i], words[j]))
            {
                dp[j] = dp[i] + 1;
            }

            ans = max(ans, dp[j]);
        }
    }

    cout << ans;

    return 0;
}

---