DeveloperOC

🔗 문제

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

📌 문제 요약

입력: 첫째 줄에 단어의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 단어가 주어진다. 단어는 알파벳 소문자로만 이루어져 있고, 길이는 최대 50이다. 집합에는 같은 단어가 두 번 이상 있을 수 있다.
출력: 접두사X 집합인 부분집합의 최대 크기를 출력한다.

💡 접근 방법

문제 유형: 정렬 + 그리디 (문자열)

“접두사 관계인 단어 쌍이 하나도 없는 최대 부분집합”을 찾는 문제다.
N이 50, 단어 길이도 50이라 사실 모든 쌍을 다 비교해도(O(N²·L)) 통과하지만,
정렬을 한 번 해두면 비교 대상이 확 줄어든다.

왜 정렬인가?
사전순으로 정렬하면 abc의 접두사인 ab는 반드시 abc보다 앞에 온다.
게다가 ab와 abc 사이에 낀 단어가 있다면 그 단어도 ab로 시작할 수밖에 없다.
즉 어떤 단어가 누군가의 접두사라면, 바로 다음 단어의 접두사이기도 하다.
그래서 인접한 두 개씩만 비교하면 충분하다.

그다음은 그리디다. words[i]가 words[i+1]의 접두사라면 둘 중 하나는 버려야 하는데,
짧은 쪽(= 앞쪽)을 버리는 게 항상 이득이다. 짧은 단어는 뒤에 오는 더 많은 단어의
접두사가 될 수 있어서 남겨두면 손해만 커지기 때문이다.

N개의 문자열을 입력 받고 오름차순으로 정렬한 뒤,
다음 인덱스의 문자열에 현재 문자열이 접두사로 사용되는지 확인하는 방식으로 구현했다.

참고로 이 풀이는 중복 단어도 자동으로 처리된다.
같은 단어는 정렬 후 붙어 있고, 자기 자신은 자기 자신의 접두사이므로 앞쪽이 그대로 걸러진다.

⚠️ 처음에 했던 실수

        if(words[i + 1].length() >= len && words[i + 1].substr(0,len) == words[i])
            continue;

해당 부분의 코드가 원래는

	if(words[i + 1].length() < len)
            continue;
	if(words[i + 1].substr(0,len) == words[i])
            continue;

이런 코드로 작성했었다.
의도는 다음 문자열보다 길이가 길면 원치않는 방향으로 조건 검사를 할까봐 다음으로 넘기도록 하는 조건이였는데
다음 문자열이 현재 문자열보다 짧으면 포함될일이 없다고 다시 생각해서 조건문을 수정했다.

💻 코드

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

int N;
string words[51];
int main()
{
    int ans = 0;
    cin >> N;

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

    // 사전순 정렬: 접두사 관계는 이제 인접한 쌍에서만 나타난다
    sort(words, words + N);

    // 마지막 원소는 뒤에 비교 대상이 없으므로 루프에서 제외
    for(int i = 0; i < N - 1; ++i)
    {
        int len = words[i].length();

        // words[i]가 words[i+1]의 접두사면 짧은 쪽(words[i])을 버린다.
        // 길이 조건을 먼저 보는 이유: 다음 단어가 더 짧으면 접두사일 수 없고,
        // substr(0, len) 자체가 불필요한 연산이 되기 때문
        if(words[i + 1].length() >= len && words[i + 1].substr(0,len) == words[i])
            continue;

        ans++;
    }

    ans++;   // 루프에서 뺀 마지막 단어는 항상 답에 포함된다

    cout << ans;
    return 0;
}

⏱️ 시간·공간 복잡도

N = 단어 개수(≤ 50), L = 단어 최대 길이(≤ 50)

N과 L이 둘 다 50이라 실제로는 연산량이 수천 번 수준이다. 제한이 아주 널널한 문제.

🔀 다른 풀이와 비교

이 문제 크기에선 셋 다 통과하지만, 정렬 방식이 구현량 대비 확장성이 제일 좋다고 느꼈다.