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

문제 링크

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

1141번: 접두사

---

◆문제 해결 및 설명◆

문제 해설 : 단어의 집합에서, 누군가의 접두사가 되는 단어가 없는 집합의 크기를 최대로 만들때, 그 집합의 크기는?

 

compareStrSize() 사용자 함수를 만들어서 string의 size를 기준으로 오름차순 정렬하였다. (긴 단어가 짧은 단어의 접두사가 될 수는 없기 때문)

2중 반복문으로 가장 짧은 단어부터 시작하여 긴 단어까지 접두사 관계를 모두 조사한다.

string의 find()를 사용하여 0을 return한다면, 접두사이므로 미리 N으로 초기화한 answer의 값을 1빼주었다.

 

코드가 깔끔하게 작성되서 코드로 보시는게 이해가 빠를 수 있다.

◆코드 전문◆

#include <vector>
#include <string>
#include <algorithm>
#include <iostream>

using namespace std;

bool compareStrSize(string str1, string str2)
{
    return str1.size() < str2.size();
}

int main()
{
    int N;
    cin >> N;
    cin.ignore();

    vector<string> strs(N);
    for (string &input : strs)
    {
        getline(cin, input);
    }
    sort(strs.begin(), strs.end(), compareStrSize);

    int answer = N;
    for (int i = 0; i < N; i++)
    {
        string prefix = strs[i];
        for (int j = i + 1; j < N; j++)
        {
            if (strs[j].find(prefix) == 0)
            {
                answer--;
                break;
            }
        }
    }
    cout << answer;
}