https://www.acmicpc.net/problem/23059
23059번: 리그 오브 레게노
첫째 줄에는 백남이가 알고 있는 아이템 사이의 관계의 수 $N$(1 ≤ $N$ ≤ 200,000)를 입력받는다. $N$개의 줄에 걸쳐서 아이템 이름을 의미하는 문자열 2개 A B가 주어진다. 아이템 A는 아이템 B를 구
www.acmicpc.net
간만에 위상정렬 문제입니다.
이 문제는 문자열을 인덱스로 변환해야 하지만 출력하는게 문자열이라 문자열 기준, 인덱스 기준의 맵을 따로 사용하였습니다.
intToString에는 인덱스 기준 문자열, stringToInt에는 문자열 기준 인덱스를 저장합니다.
이 부분이 해당 문자열에 대한 인덱스 값을 구해 맵에 넣는 과정입니다.
stringToInt와 intToString에 같이 넣어줍니다.
그 다음 위상정렬로 구매할 아이템의 순서를 정해주면 되는데
여기서 현재 같은 우선순위의 아이템은 사전 순으로 구매하기 때문에 우선순위를 인덱스로 둔 배열을 사용하였습니다.
우선순위가 낮은 (인덱스가 낮은) 배열부터 문자열들을 사전 순으로 정렬한 후에 출력합니다.
이 문제에서 N이 200000이라 MAX를 200000으로 잡았는데.. N이 문자열 갯수가 아닌 관계의 수였습니다..
이런 실수를 좀 줄여야겠습니다..
그리고 처음에는 map을 사용했었는데 시간 초과가 발생해서 unordered_map으로 바꾸니 AC를 받았습니다.
찾아보니 데이터가 많을 때 unordered_map의 성능이 훨씬 좋다고 하는 것을 보았습니다.
하지만 이 둘의 차이를 공부할 필요가 있어보입니다.
|
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
84
85
86
87
88
89
90
91
92
93
94
95
96
|
#include <iostream>
#include <unordered_map>
#include <queue>
#include <string>
#include <vector>
#include <algorithm>
#define MAX 400000
using namespace std;
typedef pair<int, int> pi;
unordered_map<int, string> intToString;
unordered_map<string, int> stringToInt;
vector<int> graph[MAX], ans[MAX];
int conn[MAX];
int N, idx;
bool cmp(int a, int b) {
return intToString[a] < intToString[b];
}
void print() {
for (int i = 0; ; i++) {
if (!ans[i].size()) return;
sort(ans[i].begin(), ans[i].end(), cmp);
for (int j = 0; j < ans[i].size(); j++) {
cout << intToString[ans[i][j]] << '\n';
}
}
}
void func() {
queue<pi> q;
for (int i = 0; i < idx; i++) {
if (!conn[i]) {
q.push({ i,0 });
ans[0].push_back(i);
}
}
for (int t = 0; t < idx; t++) {
if (q.empty()) {
cout << "-1\n";
return;
}
int x = q.front().first;
int cnt = q.front().second;
q.pop();
for (int i = 0; i < graph[x].size(); i++) {
int next = graph[x][i];
conn[next]--;
if (!conn[next]) {
q.push({ next, cnt + 1 });
ans[cnt + 1].push_back(next);
}
}
}
print();
}
void input() {
string str1, str2;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> str1 >> str2;
if (stringToInt.find(str1) == stringToInt.end()) {
stringToInt.insert({ str1, idx });
intToString.insert({ idx++, str1 });
}
if (stringToInt.find(str2) == stringToInt.end()) {
stringToInt.insert({ str2, idx });
intToString.insert({ idx++, str2 });
}
int a = stringToInt[str1];
int b = stringToInt[str2];
graph[a].push_back(b);
conn[b]++;
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > Topological-sort' 카테고리의 다른 글
| boj 2252 줄 세우기 (0) | 2021.02.07 |
|---|