문제

 

풀이

입력에는 빨간 간선인지, 파란 간선인지 주어집니다.

그러면 정점 2개를 골라서 각 정점이 포함된 연결 요소의 모든 정점들을 서로 연결시켜줍니다.

이때 사용되는 간선들 중 빨간 간선의 갯수가 최소가 되도록 정점을 적절하게 골라야 합니다.

 

처음에는 그냥 연결된 간선이 적은 정점 2개를 골라주면 되는것 아닌가? 라는 생각이 들었었고,

우선순위 큐를 이용하여 작은 값 2개의 합을 더해주는 방식으로 구현했더니 60점이 나왔었습니다.

이 방법이 맞다면 반례가 없을텐데 정답이 아닌걸로 봐서 제가 접근한 방식이 틀린거였습니다.

 

문제의 솔루션은 bfs + map을 사용하는 것이었습니다.

배열에는 각 연결요소에 포함된 정점의 갯수를 저장합니다.

N이 5라고 가정하면 처음에는 1 1 1 1 1이 배열에 저장됩니다.

그리고 이 배열의 상태를 방문처리 합니다.

 

그 다음 bfs를 통해 각 연결요소들을 2개씩 뽑아서 연결합니다.

이때 배열을 정렬해줘야 방문처리를 할 수 있습니다.

각 연결요소의 크기가 1 1 2 2인 것과 2 1 2 1인 것 둘다 똑같은 결과가 나옵니다.

그리고 그 간선이 빨간 간선일 때만 갯수를 세어줍니다.

 

해당 연결요소들의 상태가 map에 없을때만 queue에 넣어주고, map에 있을때는 최솟값을 갱신해주도록 합니다.

모든 정점이 연결되면 연결요소의 상태가 {N}이 되며, 이를 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
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define MAX 31
using namespace std;
 
int list[MAX];
int N;
 
int bfs() {
    vector<int> v = vector<int>(N, 1);
    map<vector<int>, int> m;
    m[v] = 0;
    queue<vector<int> > q;
    q.push(v);
    for (int t = 0; t < N - 1; t++) {
        int qsize = q.size();
        while (qsize--) {
            auto x = q.front();
            q.pop();
 
            int size = x.size();
            for (int i = 0; i < size - 1; i++) {
                for (int j = i + 1; j < size; j++) {
                    vector<int> tmp;
                    for (int k = 0; k < size; k++) {
                        if (i == k || j == k) continue;
                        tmp.push_back(x[k]);
                    }
                    tmp.push_back(x[i] + x[j]);
                    sort(tmp.begin(), tmp.end());
                    if (m.find(tmp) == m.end()) {
                        q.push(tmp);
                        if (!list[t]) m[tmp] = m[x] + x[i] * x[j];
                        else m[tmp] = m[x];
                    }
                    else {
                        if (!list[t]) m[tmp] = min(m[tmp], m[x] + x[i] * x[j]);
                        else m[tmp] = min(m[tmp], m[x]);
                    }
                }
            }
        }
    }
 
    return m[{N}];
}
 
void func() {
    cout << bfs() << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N - 1; i++) {
        cin >> list[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'대회 > elice' 카테고리의 다른 글

엘리스 코드 챌린지 Day 8 강림제  (0) 2024.07.23
엘리스 코드 챌린지 Day 7 계기판 조작하기  (0) 2024.07.23
엘리스 코드 챌린지 Day 5 수열 복원  (0) 2024.07.22
엘리스 코드 챌린지 Day 4 트리 위의 게임  (0) 2024.07.22
엘리스 코드 챌린지 Day 3 문자열 압축 해제  (4) 2024.07.22

문제

 

풀이

이 문제는 방법이 다양한것 같았습니다. dfs로 푸신분들도 계셨지만 저는 최근에 그리디를 좀 많이 풀었어서 그런지 그리디로 먼저 접근했습니다.

 

우선 수열이 a1, a2, a3, ... an 까지 존재한다고 했을 때 이 수열의 부분수열의 합을 2^n개 만들 수 있습니다.

하지만 문제에서 주어지는 입력은 그 부분수열의 합인 2^n개의 수가 주어집니다.

따라서 어떤 수열의 조합으로 입력되는 부분 수열의 합을 만들 수 있는지 원래 수열의 원소들을 구하는 문제입니다.

 

처음 생각해본건 두가지입니다.

1. 입력으로 주어지는 수열 중 0은 절대 답이 될 수 없음

2. 0 다음으로 제일 작은 수는 무조건 원래 수열의 원소에 해당함

1번은 원래 수열의 원소 ai의 범위는 1 ~ 100000입니다. 0을 만들려면 어떤 원소도 더하지 않는 경우밖에 없습니다.

2번은 0 다음으로 제일 작은 수는 어떤 수를 더하더라도 만들 수 없습니다. 그냥 자신만이 그 수를 만들 수 있습니다.

0 다음으로 제일 작은 수가 여러개라면 그 같은 수들을 모두 더해주도록 합니다.

 

여기서 시작해서 어떻게 그리디하게 접근할 수 있을까 고민하다가 map과 set을 사용하게 되었습니다.

map과 set에는 원래 수열로 인해 제거되는 부분 수열의 값을 저장합니다.

제가 수를 제거한 방식으로는

set에 지금까지 모은 원래 수열의 부분 수열의 합을 모두 다 저장합니다.

map에는 set에서 구한 합들을 카운팅합니다.

 

예를들어 지금까지 구한 원래 수열이 1, 2, 3라고 했을 때 얘내들의 부분 수열의 합은 0 1 2 3 3 4 5 6 입니다.

그리고 다음 추가되는 원소가 4라고 했을 때 원래 수열은 1, 2, 3, 4가 되고,

이전에서 구했던 부분 수열의 합에서 모두 +4를 해주면 4 5 6 7 7 8 9 10이 되는데,

이걸 부분 수열의 합으로 모두 추가하면 0 1 2 3 3 4 4 5 5 6 6 7 7 8 9 10이 되고, 이는 수열 1, 2, 3, 4의 부분 수열의 합이 됩니다.

 

위에서 구한 값들을 set과 map에 넣어주고,

다음 들어오는 값을 key로 map에 검색하여 1 이상으로 카운팅되어 있다면 선택하지 않고 넘어가는 방식입니다. 이때 map[key]를 1씩 감소시킵니다.

여기서 map을 사용한 이유는 원래 수열의 원소를 원래 수열의 합으로 만들 수도 있기 때문입니다.

2 4 6이 원래 수열이라면 2 + 4로도 6을 만들 수 있기 때문에 6이 걸러지는 문제가 있었습니다. 덕분에 코드가 더러워졌습니다...

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
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#define MAX 1500001
using namespace std;
 
set<int> s;
map<int, int> m;
vector<int> v;
int list[MAX];
int N;
 
void eraseNum(int x) {
    set<int>::iterator iter = s.begin();
    vector<int> tmp;
    for (; iter != s.end(); iter++) {
        tmp.push_back(*iter + x);
    }
 
    for (auto y : tmp) {
        m[y]++;
        s.insert(y);
    }
}
 
void init() {
    sort(list, list + (1 << N));
 
    v.push_back(list[1]);
    m[0]++;
    m[list[1]]++;
    s.insert(0);
    s.insert(list[1]);
    for (int i = 2; i < (1 << N); i++) {
        if (list[1] != list[i]) break;
 
        v.push_back(list[i]);
        eraseNum(list[i]);
    }
}
 
void func() {
    init();
    for (int i = 2; i < (1 << N); i++) {
        if (m.find(list[i]) != m.end()) {
            m[list[i]]--;
            if (!m[list[i]]) m.erase(list[i]);
            continue;
        }
        if (v.size() == N) break;
 
        v.push_back(list[i]);
        eraseNum(list[i]);
        for (int j = i + 1; j < (1 << N); j++) {
            if (list[i] != list[j]) break;
            if (v.size() == N) break;
            v.push_back(list[j]);
            eraseNum(list[j]);
        }
    }
 
    for (auto x : v) {
        cout << x << ' ';
    }
    cout << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < (1 << N); i++) {
        cin >> list[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'대회 > elice' 카테고리의 다른 글

엘리스 코드 챌린지 Day 7 계기판 조작하기  (0) 2024.07.23
엘리스 코드 챌린지 Day 6 빨간 선과 파란 선  (0) 2024.07.23
엘리스 코드 챌린지 Day 4 트리 위의 게임  (0) 2024.07.22
엘리스 코드 챌린지 Day 3 문자열 압축 해제  (4) 2024.07.22
엘리스 코드 챌린지 Day 2 정리 정돈을 좋아하는 k씨  (0) 2024.07.22

https://www.acmicpc.net/problem/1354

 

  • Ai = 1 (i ≤ 0)
  • Ai = A⌊i / P⌋ - X + A⌊i / Q⌋ - Y (i ≥ 1)

여기에서 An을 구하는 문제입니다.

우선 N이 10^13이기 때문에 단순 배열만으로는 해결할 수 없습니다.

그래서 처음 생각해낸건 map을 사용하여 dp를 해결하려고 했습니다.

 

dp 재귀를 돌릴 때 dp[n] != -1이면 dp[n]을 리턴했던것 처럼

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
#include <iostream>
#include <unordered_map>
using namespace std;
typedef long long ll;
 
unordered_map<ll, ll> m;
ll N, p, q, x, y;
 
ll solve(ll n) {
    if (n <= 0) return 1LL;
    if (m.find(n) != m.end()) return m[n];
    return m[n] = solve(n / p - x) + solve(n / q - y);
}
 
void func() {
    cout << solve(N) << '\n';
}
 
void input() {
    cin >> N >> p >> q >> x >> y;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

 

 

근데 생각보다 메모리를 많이 차지하고, 시간도 많이 소요되는 것을 알 수 있습니다.

다른분들의 제출 현황을 보니 이 방법은 비효율적이라는 것을 알 수 있었습니다.

 

제가 확인해봤던 풀이로는 배열을 활용하는 방법이었습니다.

하지만 N의 범위가 10^13이기 때문에 모든 범위를 배열로 해결할 수는 없습니다.

문제에서 허용하는 메모리 512MB 내에서는 가능하기 때문에 10000000 까지는 배열로, 나머지는 재귀로 해결할 수 있었습니다.

 

 

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
#include <iostream>
#include <algorithm>
#define MAX 10000001
using namespace std;
typedef long long ll;
 
ll dp[MAX];
ll N, p, q, x, y;
 
ll solve(ll n) {
    if (n < MAX) return dp[n];
 
    ll l = 1LL;
    if (n / p - x > 0) l = solve(n / p - x);
 
    ll r = 1LL;
    if (n / q - y > 0) r = solve(n / q - y);
 
    return l + r;
}
 
void init() {
    dp[0] = 1LL;
    for (int i = 1; i < MAX; i++) {
        dp[i] = dp[max(0LL, i / p - x)] + dp[max(0LL, i / q - y)];
    }
}
 
void func() {
    init();
    cout << solve(N) << '\n';
}
 
void input() {
    cin >> N >> p >> q >> x >> y;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

 

 

아까와 비교하면 메모리와 시간 차이가 정말 많이 난다는 것을 알 수 있습니다.

'algorithm > dp' 카테고리의 다른 글

boj 25378 조약돌  (0) 2024.06.29
boj 2216 문자열과 점수  (0) 2024.06.28
boj 3114 사과와 바나나  (0) 2024.06.13
boj 11560 다항식 게임  (0) 2024.06.13
boj 28018 시간이 겹칠까?  (0) 2023.08.08

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

www.acmicpc.net/problem/4195

 

4195번: 친구 네트워크

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진

www.acmicpc.net

map을 이용하여 입력으로 이름이 들어오는 순서대로 인덱스를 부여합니다.

만약 이미 인덱스가 부여된 이름이라면 map에 저장된 인덱스를 가져옵니다.

 

이제 두 친구의 인덱스가 생겼으니 union-find로 둘을 이어줍니다.

이 때 Union 함수에서 a와 b가 다를때만 친구 네트워크 수를 b만큼 a에 더해줍니다.

 

 

 

[C++]

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
#include <iostream>
#include <string>
#include <map>
using namespace std;
 
map<string, int> m;
int parent[200001];
int friends[200001];
int N, idx;
 
int find(int v) {
    if (parent[v] == v) return v;
    return parent[v] = find(parent[v]);
}
 
void Union(int x, int y) {
    int a = find(x);
    int b = find(y);
 
    if (a != b) {
        parent[b] = a;
        friends[a] += friends[b];
    }
}
 
void input() {
    string str1, str2;
    int u, v;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> str1 >> str2;
 
        if (m.find(str1) == m.end()) {
            m.insert({ str1, idx });
            parent[idx] = idx;
            friends[idx] = 1;
            u = idx++;
        }
        else {
            u = m[str1];
        }
 
        if (m.find(str2) == m.end()) {
            m.insert({ str2, idx });
            parent[idx] = idx;
            friends[idx] = 1;
            v = idx++;
        }
        else {
            v = m[str2];
        }
 
        Union(u, v);
 
        cout << friends[find(u)] << '\n';
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    int tc;
    cin >> tc;
    while (tc--) {
        input();
        m.clear();
        idx = 0;
    }
 
    return 0;
}
 cs

 

 

[Java]

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static Map<String, Integer> m = new HashMap<>();
    static int parent[][] = new int[200001][2];
    static int N, idx = 1;
 
    static int find(int v) {
        if (parent[v][0] == v)
            return parent[v][0];
        return parent[v][0] = find(parent[v][0]);
 
    }
 
    static void union(int u, int v) {
        int a = find(u);
        int b = find(v);
 
        if (a != b) {
            parent[a][1] += parent[b][1];
            parent[b][0] = parent[a][0];
        }
        sb.append(parent[a][1]).append("\n");
    }
 
    static void init() {
        for (int i = 1; i <= N * 2; i++) {
            parent[i][0] = i;
            parent[i][1] = 1;
        }
    }
 
    static void input() throws Exception {
        String str1, str2;
        int u, v;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        init();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            str1 = st.nextToken();
            str2 = st.nextToken();
 
            if (m.containsKey(str1))
                u = m.get(str1);
            else {
                m.put(str1, idx);
                u = idx++;
            }
 
            if (m.containsKey(str2))
                v = m.get(str2);
            else {
                m.put(str2, idx);
                v = idx++;
            }
 
            if (v < u) {
                int tmp = u;
                u = v;
                v = tmp;
            }
 
            union(u, v);
        }
    }
 
    public static void main(String[] args) throws Exception {
        st = new StringTokenizer(br.readLine());
        int tc = Integer.parseInt(st.nextToken());
        while (tc-- > 0) {
            input();
            m.clear();
            idx = 1;
        }
        System.out.println(sb.toString());
    }
}
 cs

'algorithm > Union-Find' 카테고리의 다른 글

boj 20040 사이클 게임  (0) 2021.06.27
boj 1043 거짓말  (0) 2021.04.05
boj 10775 공항  (0) 2021.03.17
boj 1976 여행 가자  (0) 2021.03.17
boj 1717 집합의 표현  (0) 2021.02.06

www.acmicpc.net/problem/4358

 

4358번: 생태학

프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어

www.acmicpc.net

나무의 각 종의 이름이 입력으로 들어오면 사전순으로 각 종의 비율을 출력하는 문제입니다.

사전순으로 출력하기 위해 Map 중에서 TreeMap을 사용하였습니다.

 

이름이 주어질 때마다 새로운 이름이면 생성하여 맵에넣고, 기존에 있던 이름이면 +1.0한 값을 맵에 넣어줍니다.

 

맵의 데이터들을 출력하기 위해 Entry를 사용하였고, e.getKey()(이름)과 e.getValue()/N *100 (비율)을 출력하였습니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Map.Entry;
import java.util.TreeMap;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static String st;
    static TreeMap<String, Double> m = new TreeMap<>();
    static double N;
 
    static void func() {
        StringBuffer sb = new StringBuffer();
        for (Entry<String, Double> e : m.entrySet()) {
            sb.append(e.getKey() + " " + String.format("%.4f", e.getValue() * 100.0 / N) + "\n");
        }
 
        System.out.println(sb.toString());
    }
 
    static void input() throws Exception {
        while (true) {
            st = br.readLine();
            if (st == null || st.length() == 0)
                break;
 
            if (m.containsKey(st)) {
                double a = m.get(st);
 
                m.put(st, a + 1.0);
            } else {
                m.put(st, 1.0);
            }
 
            N += 1.0;
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 cs

'algorithm > data-structure' 카테고리의 다른 글

boj 1874 수택 수열  (0) 2021.01.25
boj 17298 오큰수  (0) 2021.01.25
boj 5639 이진 검색 트리  (0) 2021.01.24
boj 1991 트리 순회  (0) 2021.01.22
boj 11003 최솟값 찾기  (0) 2021.01.22

+ Recent posts

티스토리툴바