[BOJ 14725]
문제 바로가기 : https://www.acmicpc.net/problem/14725
문제 설명은 위 링크에서 확인해주시길 바랍니다.
SolutionPermalink
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| //14725 | |
| #include <iostream> | |
| #include <string> | |
| #include <cstring> | |
| #include <cstdio> | |
| #include <vector> | |
| #include <algorithm> | |
| using namespace std; | |
| typedef long long ll; | |
| struct Node { | |
| string val; | |
| vector<Node> next; | |
| Node() {} | |
| Node(string val) : val(val) {} | |
| }; | |
| vector<Node> tree; | |
| int k; | |
| //pi : parent의 인덱스 | |
| //si : s의 | |
| void makeLink(vector<Node>& parent, vector<string> s, int pi, int si) { | |
| //종료 | |
| if (si == k) { | |
| return; | |
| } | |
| //자식 탐색 | |
| for (int i = 0; i < parent.size(); i++) { | |
| if (s[si] == parent[i].val) { | |
| pi = i; | |
| Node child; | |
| if (si < s.size() - 1) { | |
| child.val = s[si + 1]; | |
| //중복체크 | |
| bool chk = false; | |
| for (int j = 0; j < parent[pi].next.size(); j++) { | |
| if (parent[pi].next[j].val == child.val) { | |
| chk = true; | |
| break; | |
| } | |
| } | |
| if(!chk) parent[pi].next.push_back(child); | |
| } | |
| break; | |
| } | |
| } | |
| makeLink(parent[pi].next, s, pi, si + 1); | |
| } | |
| //정렬 | |
| bool compare(Node a, Node b) { | |
| return a.val < b.val; | |
| } | |
| void prt(vector<Node> parent, int hier) { | |
| //알파벳 순 출력을 위한 정렬 | |
| sort(parent.begin(), parent.end(), compare); | |
| //recursive로 답 출력 | |
| for (int i = 0; i < parent.size(); i++) { | |
| for (int j = 0; j < 2 * hier; j++) cout << '-'; | |
| cout << parent[i].val << '\n'; | |
| prt(parent[i].next, hier + 1); | |
| } | |
| } | |
| int main() { | |
| cin.tie(nullptr); | |
| cout.tie(NULL); | |
| ios_base::sync_with_stdio(false); | |
| int t; cin >> t; | |
| while (t--) { | |
| cin >> k; | |
| vector<string> tmp; | |
| for(int i=0; i<k; i++) { | |
| string value; cin >> value; | |
| tmp.push_back(value); | |
| } | |
| //중복 체크 | |
| bool chk = false; | |
| for (int i = 0; i < tree.size(); i++) { | |
| if (tree[i].val == tmp[0]) { | |
| chk = true; | |
| break; | |
| } | |
| } | |
| //process | |
| if(!chk) tree.push_back({ tmp[0] }); | |
| makeLink(tree, tmp, -1, 0); | |
| } | |
| //answer | |
| prt(tree, 0); | |
| return 0; | |
| } |
reviewPermalink
코드가 너무 더럽다. N의 범위가 적어서 통과할 수 있었지 좀만 컸어도 시간초과 당했을거 같다. 비효율의 완성..
힌트에서 트라이 알고리즘으로 풀어보라는 말이 있었는데 풀기 전에 설명이라도 읽어볼걸 그랬다😥
풀면서도 이게 되나 하면서 짰다. 다음에는 트라이로 풀어보려고 해보자.
트리 구조로 만들긴 해야 하는데 자식을 계속 담을 수 있어서 vector로 만들었다.
무슨 값이 들어있는지도 알아야 하기에 string도 멤버에 추가했다. 이를 Node로 묶고, tree가 root역할을 하도록 설정했다.
댓글남기기