반응형

문제 출처 :


https://csacademy.com/contest/archive/task/prefix-free-subset/



알고리즘 분석 :


문제 해결에 필요한 사항

1. 트라이

2. set


이 문제가 요구하는 내용은 다음과 같다.


k개의 문자열을 구해야하는데 이때 k개의 문자열들은 다음과 같은 조건을 만족해야 한다.


1. k개의 문자열 내 a, b문자열간에 prefix 관계를 가지면 안된다. (즉 a가 ban이고 b가 banana이면 a가 b의 prefix이기에 안된다.)


2. 그렇게 만든 k개의 문자열중 가장 긴 문자열을 출력해야하는데 이는 정답에서 최소여야 한다.

(즉, 정답을 다양하게 만들 수 있지만 가장 최소의 길이를 가지는 가장 긴 문자열을 만들어야 한다.)


따라서 우리는 2번을 만족시키기 위해 길이 순으로 정렬을 한번 해준다.


이제 1번을 만족시키기 위해 우리는 트라이를 생성한다.


트라이를 이용할 때 isEnd = true인 부분을 만나게 되면 이전에 들어온 문자열이 현재 내가 진행하고 있는 문자열의 prefix라는 것을 의미한다.


따라서 그에 해당하는 것은 set에서 제거해주고, 방금 들어온 문자열은 set에 추가해줌을 반복한다.


set의 크기가 k와 같아지는 순간이 문제에서 요구하는 내용이고 그때 문자열의 길이가 문제의 정답이 된다.


만약 k를 만족하는 답이 없을경우는 -1을 출력한다.






소스 코드 : 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <set>
 
using namespace std;
 
set<string> st;
 
string str[1000002];
 
const int MAX_NODE = 26;
 
bool comp(const string &a, const string &b)
{
    return a.size() < b.size();
}
struct Trie {
    Trie *next[MAX_NODE];
    int isEnd;
 
    Trie() {
        for (int i = 0; i < MAX_NODE; i++)
            next[i] = nullptr;
        isEnd = false;
    }
    ~Trie() {
        for (int i = 0; i < MAX_NODE; i++)
            if (next[i])
                delete next[i];
    }
};
 
int main()
{
    int n, k;
    cin >> n >> k;
 
    for (int i = 0; i < n; i++)
        cin >> str[i];
 
    sort(str, str + n, comp);
 
    Trie *root = new Trie;
 
    for (int i = 0; i < n; i++)
    {
        Trie *pos = root;
 
        int len = str[i].size();
        bool chk = false;
        for (int j = 0; j < len; j++)
        {
            int nowCh = str[i][j] - 'a';
 
            if (!pos->next[nowCh])
                pos->next[nowCh] = new Trie;
            
            if (pos->next[nowCh]->isEnd)
            {
                string tmp = str[i].substr(0, j + 1);
                st.erase(tmp);
            }
 
            pos = pos->next[nowCh];
        }
 
        st.insert(str[i]);
 
        if (k == st.size())
            return !printf("%d\n", str[i].size());
            
        pos->isEnd = true;
    }
    
    printf("-1");
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus

반응형

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[9494번] 데구르르  (0) 2018.03.19
[1342번] 행운의 문자열  (0) 2018.03.17
[9202번] Boggle  (0) 2018.03.10
[5446번] 용량 부족  (0) 2018.03.08
[1744번] 수 묶기  (0) 2018.03.08