[Week 6] DICTIONARY self review - Yunhyunjo
Opened this issue · 0 comments
Yunhyunjo commented
DICTIONARY self review
1. 해결 시도 과정
위상정렬을 위해 indegree와 ch를 선언하여 저장하고 인접리스트를 만들어 정렬을 시도하였습니다.
2. 작성한 코드와 설명
while (c--) {
string s, p;
fill(indegree.begin(), indegree.end(), 0);
fill(ch.begin(), ch.end(), 0);
vector <vector <int>> v(26);
cin >> n >> s;
p = s;
ch[p[0] - 97] = 1;
for (int i = 1; i < n; i++) {
cin >> s;
if (p[0] != s[0]) {
if (ch[s[0] - 97] == 0) ch[s[0] - 97] = 1;
indegree[s[0] - 97]++;
v[p[0] - 97].push_back(s[0] - 97);
}
else {
int pp = 1;
while (pp < p.size() && pp < s.size()) {
if (p[pp] != s[pp]) {
if (ch[p[pp] - 97] == 0) ch[p[pp] - 97] = 1;
if (ch[s[pp] - 97] == 0) ch[s[pp] - 97] = 1;
indegree[s[pp] - 97]++;
v[p[pp] - 97].push_back(s[pp] - 97);
break;
}
pp++;
}
}
p = s;
}
cout << topologySort(v) << endl;
}
먼저 입력된 순서대로 비교하여 인접리스트를 만들고 indegree도 구해주었습니다.
두 단어의 0번째 값이 같을 경우에는 다음 인덱스의 해당하는 문자를 비교해주었습니다.
그렇게 구한 인접리스트를 topologySort함수에 매개변수로 넘겨주어 위상정렬을 해 출력해 주었습니다.
string topologySort(vector <vector <int>>& v) {
string s = "";
queue <int> q;
for (int i = 0; i < 26; i++) {
if (ch[i] == 1 && indegree[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
int x = q.front();
q.pop();
char c = x + 97;
s += c;
for (int j = 0; j < v[x].size(); j++) {
if (v[x][0] == 50) return "INVALID HYPOTHESIS";
if (--indegree[v[x][j]] == 0) q.push(v[x][j]);
}
v[x].clear();
v[x].push_back(50);
}
if(s == "") return "INVALID HYPOTHESIS";
for (int i = 0; i < 26; i++) {
if (ch[i] == 0) {
char c = i + 97;
s += c;
}
}
return s;
}
queue를 사용하여 일단 indegree값이 0인 값을 넣어주었습니다. 그 다음 bfs를 통해 위상정렬을 해 주었습니다.
순환을 막기위해 이미 정렬에 사용한 정점 리스트는 clear해준 다음 값 50을 넣어주었고, for 문을 돌때 0번째 값이 50이면 이미 정렬에 사용한 정점으로 순환된 것 이므로 바로 INVALID HYPOTHESIS를 리턴해주었습니다.
또 indegree가 0인 것이 없어 s가 비어있을 경우에도 순환이란 뜻이므로 INVALID HYPOTHESIS를 리턴해주었습니다.
3. 막힌 점 및 개선 사항
예제 입력은 정답이 제대로 나와서 정확히 어디서 틀린지를 모르겠습니다. 만약 똑같은 순서가 중복으로 나올 때 어차피 topologySort함수에서 걸러지므로 인접리스트 만들때 처리를 안해줬는데 처리하는 코드를 넣어줘야할 것 같습니다.