카카오 1차 온라인 테스트

1. 풀이법 : map

#include <string>
#include <vector>
#include <map>
using namespace std;
 
string names[100001];
string Enter = "Enter";
string Leave = "Leave";
string Change = "Change";
 
vector<string> solution(vector<string> record) {
    map<string, int> m;
    int cnt = 0;
    vector<string> answer;
    // id_cnt, action
    vector<pair<int, int>> ans;
    string command, uid, name;
    for (auto s : record) {
        int idx1, idx2;
 
        for (idx1 = 0; s[idx1] != ' '; ++idx1);
        command = s.substr(0, idx1);
 
        for (idx2 = ++idx1; idx2 < s.length() && s[idx2] != ' '; ++idx2);
        uid = s.substr(idx1, idx2 - idx1);
 
        if (command == Leave) {
            ans.push_back({ m[uid], 1 });
            continue;
        }
 
        name = s.substr(idx2 + 1, s.length() - idx2 - 1);
 
        if (command == Enter) {
            if (m.count(uid)) {
                names[m[uid]] = name;
            }
            else {
                m.insert({ uid, ++cnt });
                names[cnt] = name;
            }
            ans.push_back({ m[uid], 0 });
        }
        else if (command == Change) {
            names[m[uid]] = name;
        }
    }
    string com;
    for (auto i : ans) {
        string com = names[i.first];
        if (i.second == 0) {
            com += "님이 들어왔습니다.";
        }
        else {
            com += "님이 나갔습니다.";
        }
        answer.push_back(com);
    }
    return answer;
}

2. 풀이법 : 누적합

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int d[505];
 
vector<int> solution(int N, vector<int> stages) {
    vector<pair<double, int>> ans;
    for (auto i : stages) 
        d[i]++;
    for (int i = N; i >= 1; --i) {
        d[i] += d[i + 1];
        ans.push_back({ -double(d[i] - d[i + 1]) / double(d[i]), i });
    }
    sort(ans.begin(), ans.end());
    vector<int> answer;
    for (auto i : ans)
        answer.push_back(i.second);
    return answer;
}

3. 풀이법 : 순열 + map

#include <string>
#include <vector>
#include <set>
using namespace std;
 
set<string> s[1<<8];
set<string> ss[8];
bool c[8];
int answers[257], ccnt;
 
inline int ctz(int a) {
    int r = 0;
    while (!(a & 1)) a >>= 1, r++;
    return r;
}
 
int solution(vector<vector<string>> relation) {
    int answer = 0;
    int siz = relation[0].size();
    for (auto i : relation) {
        for (int j = 0; j < siz; ++j) {
            if (ss[j].count(i[j])) {
                c[j] = 1;
            }
            else {
                ss[j].insert(i[j]);
            }
        }
    }
    for (int i = 0; i < siz; ++i) answer += c[i] == 0;
    for (int cnt = 2; cnt <= siz; ++cnt) {
        // cnt 개를 뽑아서 만드는 경우를 모두 만든다
        int p = (1 << cnt) - 1;
        int maxp = 1 << siz;
        while (p < maxp) {
 
            bool f = 1;
            for (int j = 0; j < siz; ++j) {
                // 단일 항목으로 후보키가 될 수 있는게 섞여있으면 최소성 불만족
                if ((!c[j] && p&(1 << j))) {
                    f = 0;
                    break;
                }
            }
            if (f) {
                f = 1;
                for (int j = 0; j < ccnt; ++j) {
                    // 후보키중 하나를 아예 포함한다면 최소성 불만족
                    if ((answers[j] & p) == answers[j]) {
                        f = 0;
                    }
                }
                if (f) {
                    for (auto j : relation) {
                        string com = "";
                        for (int k = 0; k < siz; ++k) {
                            if (p&(1 << k))
                                com += j[k];
                        }
                        if (s[p].count(com)) {
                            f = 0;
                            break;
                        }
                        else {
                            s[p].insert(com);
                        }
                    }
                    if (f) {
                        answers[ccnt++] = p;
                        answer++;
                    }
                }
            }
            int t = p | (p - 1);
            p = (t + 1) | (((~t&-~t) - 1) >> (ctz(p) + 1));
        }
    }
    return answer;
}

4. 풀이법 : 펜윅트리

음식 양에 대해 오름차순으로 정렬한 후 하나씩 먹어가면서 현재꺼 먹었을 때 k이상이 된다면 거기선 O(n)으로 하나씩 그냥 찾는다.

O( 2e6 * log2e6)

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
 
pair<int, int> arr[200001];
int pt[200021];
ll siz;
int ch[200021];
 
int sum(int i) {
    int ans = 0;
    while (i > 0) {
        ans += pt[i];
        i -= (i&-i);
    }
    return ans;
}
 
void update(int i, int dif) {
    while (i <= siz) {
        pt[i] += dif;
        i += (i&-i);
    }
}
 
int solution(vector<int> food_times, long long k) {
    int answer = 0;
    siz = food_times.size();
    arr[0] = { 1,0 };
    for (int i = 0; i < food_times.size(); ++i) {
        arr[i + 1] = { food_times[i], i + 1 };
        update(i + 1, 1);
        ch[i + 1] = 1;
    }
    sort(arr + 1, arr + food_times.size() + 1);
 
    ll cur = -1;
    for (int i = 1; i <= food_times.size(); ++i) {
        ll times = arr[i].first - arr[i - 1].first;
 
        int seg = 0;
 
        if (arr[i - 1].second < arr[i].second) {
            seg = sum(arr[i].second - 1) - sum(arr[i - 1].second);
        }
        else {
            times--;
            seg = sum(siz) - sum(arr[i - 1].second)    + sum(arr[i].second - 1);
        }
        ll dif = times * (siz + 1 - i) + seg + 1;
        if (k <= cur + dif) {
            cur += sum(arr[i].second) - sum(arr[i - 1].second - 1);
            
            ll cnt = (k - cur) / (siz + 1 - i);
            cur += (siz + 1 - i)*cnt;
            int pos = arr[i].second;
            if (cur == k) {
                return pos;
            }
            else if (cur > k) {
                while (cur != k) {
                    pos--;
                    if (pos == 0) pos = siz;
                    while (!ch[pos]) {
                        pos--;
                        if (pos == 0) pos = siz;
                    }
                    cur--;
                }
            }
            else {
                while (cur != k) {
                    pos++;
                    if (pos == siz + 1) pos = 1;
                    while (!ch[pos]) {
                        pos++;
                        if (pos == siz + 1) pos = 1;
                    }
                    cur++;
                }
            }
            return pos;
        }
        update(arr[i].second, -1);
        ch[arr[i].second] = 0;
        cur += dif;
    }
    return -1;
}

5. 풀이법 : 세그먼트 트리

0~100000 사이에서 제일 높은것 = 루트

그 루트의 x위치를 기준으로 왼쪽, 오른쪽 구역으로 나눠서 dfs타듯이 들어가면서

세그먼트 트리로 최대값을 찾으면 그게 l_child, r_child가 된다.

O(sum(klog(1e6/k)))인데 울프람에서 그려보니 매번 풀맵 서치한다고 했을 때 k=20일 때 O(2000)이다.

결국 세그먼트 트리 만드는데 시간이 더걸린다.

#include <string>
#include <vector>
#include <algorithm>
#include <memory.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
int adj[1 << 17][2];
pair<int, int> arr[1 << 20];
int siz;
int xpos[1 << 17];
 
void update(int i, int val, int idx) {
    i += siz;
    arr[i].first = val;
    arr[i].second = idx;
    while (i > 1) {
        i /= 2;
        arr[i] = arr[i * 2].first < arr[i * 2 + 1].first ? arr[i * 2 + 1] : arr[i * 2];
    }
}
 
pair<int, int> _max(int L, int R, int nodeNum, int nodeL, int nodeR) {
    if (R<nodeL || L>nodeR) return { -1,-1 };
    if (L <= nodeL && R >= nodeR) return arr[nodeNum];
    int mid = (nodeL + nodeR) / 2;
    pii l = _max(L, R, nodeNum * 2, nodeL, mid);
    pii r = _max(L, R, nodeNum * 2 + 1, mid + 1, nodeR);
    return l.first > r.first ? l : r;
}
 
vector<int> ans1;
vector<int> ans2;
 
// 현재 위치 rnN
void dfs(int l, int r, int rnN) {
    if (r < l) return;
    ans1.push_back(rnN);
    auto left = _max(l, xpos[rnN] - 1, 1, 0, siz - 1);
    if (left.first != -1) {
        adj[rnN][0] = left.second;
        dfs(l, xpos[rnN] - 1, left.second);
    }
 
    auto right = _max(xpos[rnN] + 1, r, 1, 0, siz - 1);
    if (right.first != -1) {
        adj[rnN][1] = right.second;
        dfs(xpos[rnN] + 1, r, right.second);
    }
    ans2.push_back(rnN);
}
 
vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    siz = 1 << 17;
    memset(arr, -1, sizeof(arr));
    for (int i = 0; i < nodeinfo.size(); ++i) {
        // x = nodeinfo[i][0]
        // y = nodeinfo[i][1]
        update(nodeinfo[i][0], nodeinfo[i][1], i + 1);
        xpos[i + 1] = nodeinfo[i][0];
    }
    // first = height, second = nodeNum
    pair<int, int> root = _max(0, 100001, 1, 0, siz - 1);
    dfs(0, 100001, root.second);
    //dfs1(root.second);
    //dfs2(root.second);
    
    vector<vector<int>> answer;
    answer.push_back(ans1);
    answer.push_back(ans2);
 
 
    return answer;
}