BOJ - 1141번 접두사(C++)

문제 출처: https://www.acmicpc.net/problem/1141

문제 난이도

Silver 2

문제 접근법

접두사가 되는 애들만 체크해서 빼면 가장 큰 부분집합를 이루는 수가 된다.

통과 코드

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

using namespace std;

struct str {
	string s;
	int len;
	str(string ss, int l) {
		s = ss;
		len = l;
	}

	bool operator<(const str &d) {
		return len < d.len;
	}
};
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N,res=0;
	cin >> N;
	vector<str> s;
	for (int i = 0; i < N; i++) {
		string tmp;
		cin >> tmp;
		s.push_back(str(tmp, tmp.size()));
	}
	sort(s.begin(), s.end());
	for (int i = 0; i < s.size(); i++) {
		bool hasPrefix = false;
		for (int j = i + 1; j < s.size(); j++) {
			if (s[j].s.find(s[i].s) == 0 ) {
				 hasPrefix = true;
			}
		}
		if (hasPrefix) res++;
	}
	cout << N-res << "\n";

	return 0;
}

피드백

표시된 난이도보다 시간을 더 많이 쓰고 삽질을 많이 했다... 처음에 문제를 잘못이해해서 접두사가 아닌 것 중에 제일 큰 길이의 단어 수인 줄 알았고 계속 답이 안나와 자세히보니깐 부분집합 중 가장 큰 수였다.
심지어 처음에는 어?접두사? Trie 사용해볼까?하고 썼다가 계속 답이 안나왔다!
어떻게 이용하면 될 것 같은데 초반부터 문제를 잘못이해해서 그런가 꼬였다.
그래서 다른 쉽게.. 단순하게 생각해서 푼 풀이를 봤고 바로 구현했다. 알고리즘 적으로 어려운건 없는데 꼬여서 생각하다보니 어렵게 느껴졌다..