[C++]Baekjoon 1141번: 접두사

1. 문제

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

1141번: 접두사

 

N개의 단어가 주어졌을때, 접두사X 집합의 최대 크기를 구하는 문제이다.

 

즉, 어떤 단어가 다른 단어의 접두사가 되지 않는 단어의 갯수를 찾으면 된다.

 

2. 풀이

접두사를 찾는 문제라는 것을 인지하니 정렬이 떠올랐다.

 

sort()를 활용하여 정렬을 하면, 사전처럼 접두사가 될 수 있는 단어가 다른 단어들의 앞에 정렬되기 때문이다.

 

정렬을 하고 난 후에는 substr() 을 활용해서 해당 단어가 뒤에 나오는 단어들의 접두사가 맞는지 확인한다.

 

만약에 접두사가 맞다면, 접두사를 제외하는 의미로 cnt의 개수를 한개 빼준다.

 

cnt는 처음에는 전체 단어의 개수로 설정해준다.

 

3. 코드

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int main() {

    int num;

    string s; // 단어를 입력받을 때 사용할 문자열

    vector<string> v; // 비교할 단어들의 집합

    string temp; // 접두사인지 검증받을 단어를 임시로 저장해줄 문자열

    cin >> num;

    for (int i = 0; i < num; i++) { // 단어 입력 받아서 vector에 저장

        cin >> s;

        v.push_back(s);

    }

    sort(v.begin(), v.end()); // 정렬

    int cnt = num; // 접두사가 아닌 단어의 개수, 처음에는 전체단어이고 접두사로 판정되면 1씩 빼준다

    for (int i = 0; i < num-1; i++) { // 마지막에는 한칸 덜감 (i+1 번째까지 비교하기 때문)

        temp = v[i]; // 정렬 후 접두사인기 검증될 단어를 temp에 저장

        int j = v[i].size(); // 접두사의 후보의 크기를 저장

        if (temp == v[i+1].substr(0,j)) // substr() 활용하여 부분문자열을 비교한다

            cnt--; // 다른 단어의 접두사가 되는 단어가 존재한다면 cnt--;

    }

    cout << cnt;

    return 0;

}

 

4. 느낀점

substr()을 활용하여 부분 문자열을 추출하는 방법을 배운 문제였다.

 

substr()은 std::string 클래스에서 사용할 수 있는 함수로, 문자열의 일부분을 추출하는 데 사용된다.

 

인자로는 시작 인덱스와 추출할 부분 문자열의 길이(없으면 끝까지)를 받는다.

 

이 문제에서는 단어의 처음부터 접두사의 길이만큼을 추출해서 해당 단어에 접두사가 포함되어 있는지 확인했다.

 

그리디 알고리즘에 관한 포스팅을 쓰면서 정렬과 세트로 나오는 경우가 많다는 것을 인지했다. 

 

그리고 접두사라고 하니까 사전 순이 바로 생각나서 정렬을 해야겠다는 생각이 금방 떠올랐다.

 

정렬하고 난 후에는 위에서 언급한 substr()을 이용하여 접두사인지 확인했다.

 

좋은 알고리즘은 아닌 것 같지만 다행도 연산 수가 적어서 해결할 수 있었다.

 

오늘 하루도 쌓였다!