프로그래밍

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

[난이도] Gold2
[유형] Trie

[풀이]
Trie 문제인데 정렬을 이용하여 간단히 풀 수 있습니다.
출력을 할 때, 먹이정보가 오름차순으로 빠른 순서인 개미의 정보부터 출력을 해야합니다.
예를 들어, A B C E 보다 A B C D 인 먹이정보를 가져온 개미의 정보부터 출력을 해야합니다.
각 개미의 먹이정보를 vector<string>에 넣은 뒤 정렬하면 vector의 comparator에 의해 저절로 오름차순으로
정렬이 되기 때문에
정렬 된 이후 0~N-1 번 개미의 먹이정보를 순차적으로 출력해주면 됩니다.

i-1번 개미 : A B C D
  i번 개미 : A B C E

먹이정보가 위와 같은 경우에는
i번 개미의 정보를 찍을 때, A,B,C는 이미 i-1번 개미의 정보를 찍을 때 찍은 E의 조상 노드이므로
출력을 하면 안됩니다.
이를 확인하기 위해 단순하게 i번 개미의 먹이정보를 출력하기 전에 i-1번 개미의 먹이정보가 비교해서
i-1,i가 같은 먹이 (위의 예시에서 A,B,C) 까지는 출력을 하지 않으면 됩니다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int N,K;
vector<string> v[1000]; 
string line(int k){
    string ret;
    while(k--) ret+="--";
    return ret;
}
int main(){
    cin >> N;
    for(int i=0;i<N;i++){
        vector<string> t;
        cin >> K;
        while(K--){
            string s;
            cin >> s;
            t.push_back(s);
        }
        v[i]=t;
    }
    sort(v,v+N);
    for(int i=0;i<N;i++){
        int d=0;
        if(i!=0){
            for(int j=0;j<v[i].size()&&j<v[i-1].size();j++){
                if(v[i][j]==v[i-1][j]) d++;
                else break;
            }
        }
        for(int j=d;j<v[i].size();j++) cout << line(j)+v[i][j] << '\n';
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold2/14725.cpp

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

[난이도] Gold4
[유형] Map, Trie

[풀이]
종의 이름을 key로 하는 (string,int) pair의 map을 만들어서
해당 종의 총 갯수를 구하면 된다.

나무 이름에 공백이 있을 수도 있으므로 한줄 전체를 입력으로 받아야 한다.
getline(cin,s) 함수를 이용하면 한줄을 단위로 입력받을 수 있다.
EOF 같은 경우 아래와 같이 처리해주면 파일이 끝날 때 while문을 빠져나가게 된다.
while(getline(cin,s)){

}

Trie로 풀면 더 빠른시간내에 해결할 수 있다고 한다.

#include <iostream>
#include <map>
#include <string>
#include <cmath>
using namespace std;
map<string,int> m;
int n;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s;
    while(getline(cin,s)){
        m[s]++;
        n++;
    }
    for(auto k : m){
        double b = 100*k.second / (double)n;
        printf("%s %.4lf\n",k.first.c_str(),b);
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/4358.cpp