시간복잡도, 중요포인트, 실수할만한 부분 위주로 설명하겠습니다.
개인정보 수집 유효기간 - LV. 1, 구현
해설
보편적인 날짜 계산문제입니다.
여러 풀이를 봤지만 가장 쉬워보이는 풀이는
날짜를 모두 day로 변환해 비교함이 가장 편해보입니다.
또한 각 알바펫 별로 Term이 정해져 있으므로
int 배열에 아스키코드 - 'A'를 인덱스로 하는 배열에
Term을 저장합니다.
이제 각 날짜에 해당하는 Term을 더해주고
요구사항대로 판단하면 됩니다. (밑에서 더 설명합니다)
시간복잡도는 숫자 범위들이 워낙 작아서
따로 판단하지 않아도 될 것 같습니다.
+) 문자열의 구분 인덱스가 고정되어 있으므로 C++에서는
split 함수를 만들기 보다 substr 함수를 이용해서 가볍게 잘라주는 편이
더 편하다고 생각합니다.
실수할만한 부분
날짜를 더해서 어느 조건일 때 정답 벡터에 넣을 것인지 예민하게 짚고 넘어가야 합니다.
편하게 생각하기 위해 개인정보 수집일자를 n일이라고 하고, 유효기간을 1일이라고 하면
n일까지는 개인정보를 수집하고 있어야하므로
만료일은 n+1일이 되어야합니다.
때문에 만료일자 = 수집일자 + 유효기간 이 성립하게 됩니다.
그리고 만료일자가 Today보다 같거나 크다면
오늘 기준에서 이미 만료된 개인정보이므로 정답 벡터에 넣어줍니다.
소스코드 :
#include <string> #include <vector> using namespace std; int today; int term[26]; vector<int> ans; vector<int> solution(string todays, vector<string> terms, vector<string> privacies) { // change to Day today = stoi(todays.substr(0, 4))*12*28 + stoi(todays.substr(5,2))*28 + stoi(todays.substr(8)); // make Term for (string s: terms) term[s.front()-'A'] = stoi(s.substr(2))*28; // change to day and add term for (int i=1; i<= privacies.size(); i++) { string s = privacies[i-1]; int day = 0; // day: 만료일자 day += term[s.back()-'A']; day += stoi(s.substr(0, 4)) * 12 * 28; day += stoi(s.substr(5, 2)) * 28; day += stoi(s.substr(8, 2)); if (day <= today) ans.push_back(i); } return ans; }
택배 배달과 수거하기 - Lv. 2, 그리디, 구현
그리디 대상, 해설
항상 가장 먼 집부터 배달, 수거 해야합니다.
적당히 증명해보자면
가장 먼 집의 최소 방문 횟수는 정해져 있습니다.
이 때 먼 집부터 방문한다면 방문횟수를 최소로 다녀올 수 있지만
다른 집부터 방문하다가 먼 집을 방문하게 되면
먼 집을 추가로 방문해야 할 수 있습니다.
이 때 이동 거리는 계속 증가하게 됩니다.
우선 가장 먼 집부터 배달을 먼저 합시다.
또한 배달할 수 있는 공간이 남는다면 가는길에 같이 배달합니다.
배달을 모두 완료하면 트럭은 비어있습니다.
이제 되돌아 가는길에 먼 집부터 가능한만큼 수거하면 됩니다.
이제 구현측면에서 이야기 해봅시다.
n의 값이 십만이므로 적은 상수번의 순회정도로 끝을 봐야합니다.
즉 마지막 집에서 첫 집까지 순회하면서 문제를 해결함이 좋아보입니다.
이 때 deliveries, pickups의 원소크기가 50이하라는 점에 주목합시다.
원소의 크기에 n을 곱해도 오백만정도 일것이므로
각 집에서 상자를 cap씩 배송, 수거해도 상관없습니다.
그리괴 마지막에 cap보다 작은 상자가 남아있다면
이를 변수에 저장해놓고, 다음 집에 갔을 때 이미 배송, 수거했다고 가정한 후 풀이하면 됩니다.
시간복잡도
d = deliveries 원소의 크기
p = pickups 원소의 크기
최악의 경우를 고려합시다
cap = 1, d = p = 50, n = 100,000
5백만 이므로 충분히 시간안에 해결됩니다.
소스코드
#include <string> #include <vector> #include <algorithm> using namespace std; typedef long long ll; // tp: 이미 수거한 상자 수 // td: 이미 배달한 상자 수 ll tp, td; ll ans; ll solution(int cap, int N, vector<int> pick, vector<int> dlv) { for (int i=N-1; i>=0; i--) { int cnt = 0; // 걸음 수 int p = pick[i]; p -= tp; // 수거해야하는 상자 수 int d = dlv[i]; d -= td; // 배달해야하는 상자 수 tp = td = 0; // 배송, 수거 시작 while (p > 0 || d > 0) { p -= cap; d -= cap; cnt += (i+1)*2; } // 배달, 수거한 다른 집 저장 tp -= p, td -= d; // 걸음걸이 더해주기 ans += cnt; } return ans; }
이모티콘 할인 행사 - Lv. 2, 브루트포스
해설
저는 이 문제가 제일 쉬웠습니다.
emotions의 길이가 7이므로 10, 20, 30, 40% 의 모든 경우를 고려해도 됩니다.
7개의 for문을 사용하면 너무 더러워지므로, 재귀함수를 이용합시다.
그리고 경우마다 사용자마다 이모티콘을 사고, 일정 금액이 넘어가면 서비스에 가입하서 비교하면 풀립니다.
시간복잡도
e = length of emotions
u = length of users
슬슬 귀찮으니 직접 계산 해보세요
소스코드
#include <string> #include <vector> using namespace std; vector<vector<int>> U; vector<int> E, sales; int n, m; pair<int, int> result; void f() { pair<int, int> info = {0, 0}; for (auto v: U) { int byS = v[0], mx = v[1]; int sum = 0; for (int i=0; i<m; i++) if (byS <= sales[i]) sum += E[i]*(100-sales[i])/100; if (sum >= mx) info.first++; else info.second += sum; } result = max(result, info); } void C(int idx) { if (idx == m) { f(); return; } for (int i=10; i<=40; i+=10) { sales.push_back(i); C(idx+1); sales.pop_back(); } } vector<int> solution(vector<vector<int>> tU, vector<int> tE) { U = tU, E = tE; n = U.size(), m = E.size(); C(0); return {result.first, result.second}; }
표현 가능한 이진트리 - Lv.3, 분할정복
해설
포화 이진트리는 모든 리프노드의 레벨이 같습니다. 또한
포화 이진트리 노드의 개수는 레벨에 따라 모두 같다는 점이 중요합니다.
트리의 높이를 H라고 했을 때 노드의 개수는 2^H-1입니다.
그리고 노드의 개수는 이진수의 길이가 됩니다.
때문에 숫자를 이진수로 변환한 후 이진수의 앞에 더미노드인 0을 부족한 길이만큼 추가합니다.
(앞에 추가해야하는 이유는 다른곳에 추가하면 숫자가 변하게됩니다)
0을 추가한 후 트리의 조건을 만족하지 못하는 경우는
부모노드가 0인데 자식노드 중 1이 존재하는 경우입니다.
분할정복을 통해 이를 확인하면 됩니다.
시간복잡도
마스터 정리를 이용합시다
T(n) = T(n/2) + n 이므로
O(n) 입니다.
소스코드
#include <string> #include <vector> #include <algorithm> #include <iostream> using namespace std; typedef long long ll; string tree; int n; vector<int> rtn; bool isAllZero(int lo, int hi) { for (int i=lo; i<=hi; i++) if (tree[i] != '0') return false; return true; } bool isBinaryTree(int lo, int hi) { if (lo == hi) return true; int mid = (lo+hi)>>1; if (tree[mid] == '0') { if (!isAllZero(lo, mid-1) || !isAllZero(mid+1,hi)) return false; } else { if (!isBinaryTree(lo,mid-1) || !isBinaryTree(mid+1,hi)) return false; } return true; } string toBinary(ll n) { string rtn = ""; while (n != 0) { rtn += n%2+'0', n /= 2; } ll len = 1; while (len <= rtn.size()) len *= 2; len -= 1; len -= rtn.size(); while (len--) rtn += '0'; reverse(rtn.begin(), rtn.end()); return rtn; } vector<int> solution(vector<long long> numbers) { for (ll v: numbers) { tree = toBinary(v); n = tree.size(); if (n%2 == 0 || tree[n/2]=='0') { rtn.push_back(0); continue; } rtn.push_back(isBinaryTree(0, n-1)); } return rtn; }
표 병합 - Lv.3, 분리집합, 구현
해설
분리집합을 사용해서 각 표가 병합될 때 마다
각 표들을 합쳐주면 됩니다.
그런데, 굳이 분리집합을 사용할 필요가 없었습니다.
그냥 배열 하나 두고, 분리집합처럼 사용하면 됩니다.
분리집합에서는 두 집합을 합칠 때
두 집합의 원소 중 하나씩 합쳐주면
두 집합이 합쳐집니다.
이를 배열로 구현하려면
두 집합 중 하나의 집합의 모든원소를 순회하면서 다른 집합에 합쳐주여야합니다.
또한 집합을 해체하는 과정에서 분리집합은 중간에 트리가 끊어지면,
자식노드는 루트노드로 이동할 수 없어집니다.
즉, 끊어진 노드의 자식노드는 해체가 불가능해집니다.
때문에 해체할때는 모든 원소를 순회하면서 집합의 원소를 따로 담아둔 후,
한번에 해체시켜주어야 합니다.
이를 배열로 구현한다면 합칠때와 똑같이 모든 원소를 순회하면서 하나씩 해체해주면 됩니다.
시간복잡도
모든 원소를 순회하는 과정이 제일 오래걸리므로
간단히
O(N^2)
으로 결론지을 수 있습니다.
소스코드
저는 분리집합으로 풀었습니다.
#include <string> #include <vector> #include <sstream> #include <iostream> #define f first #define s second using namespace std; typedef pair<int, int> pii; struct Disjoint_set { public: pii parent[51][51]; Disjoint_set() { for (int i=1; i<=50; i++) for (int j=1; j<=50; j++) parent[i][j] = {i, j}; } pii root(pii x) { if (parent[x.f][x.s] == x) return x; return parent[x.f][x.s] = root(parent[x.f][x.s]); } void uni(pii tx, pii ty) { pii x = root(tx), y = root(ty); if (x == y) return; parent[y.f][y.s] = x; } bool isUni(pii x, pii y) { return root(x) == root(y); } }; string table[51][51]; vector<string> ans; Disjoint_set uf = Disjoint_set(); vector<string> split(string s, char c) { vector<string> rtn; stringstream ss(s); string buffer; while (getline(ss, buffer, c)) rtn.push_back(buffer); return rtn; } vector<string> solution(vector<string> commands) { for (auto s: commands) { vector<string> v = split(s, ' '); if (v[0] == "UPDATE" && v.size() == 4) { string value = v[3]; auto [r, c] = uf.root({stoi(v[1]), stoi(v[2])}); table[r][c] = value; } else if (v[0] == "UPDATE" && v.size() == 3) { string value1 = v[1], value2 = v[2]; for (int i=1; i<=50; i++) { for (int j=1; j<=50; j++) { auto [r, c] = uf.root({i, j}); if (table[r][c] == value1) table[r][c] = value2; } } } else if (v[0] == "MERGE") { int r1 = stoi(v[1]), c1 = stoi(v[2]), r2 = stoi(v[3]), c2 = stoi(v[4]); pii root1 = uf.root({r1, c1}), root2 = uf.root({r2, c2}); if (table[root1.f][root1.s].empty()) uf.uni({r2, c2}, {r1, c1}); else uf.uni({r1, c1}, {r2, c2}); } else if (v[0] == "UNMERGE") { int v1 = stoi(v[1]), v2 = stoi(v[2]); auto [r, c] = uf.root({v1, v2}); string temp = table[r][c]; vector<pii> merged; for (int i=1; i<=50; i++) for (int j=1; j<=50; j++) if (uf.isUni({r, c}, {i, j})) merged.push_back({i, j}); for (auto [f, s]: merged) { table[f][s] = ""; uf.parent[f][s] = {f, s}; } table[v1][v2] = temp; } else { auto [r, c] = uf.root({stoi(v[1]), stoi(v[2])}); ans.push_back(table[r][c].empty() ? "EMPTY" : table[r][c]); } } return ans; }
미로 탈출 명령어 - Lv. 3, 그리디
해설
여러가지 중구난방으로 이야기할 수 있겠으나,
그리디 문제가 옳아보이고
결국 중요한 포인트는 d, l, r, u 순으로
특정 조건을 만족한다면 무조건 이동해야합니다.
불가능한 케이스는 k번을 모두 이동했음에도 특정 조건을 만족하지 못한경우입니다.
특정 조건은 다음 좌표가 표에서 벗어나지 않고,
남은 이동횟수가 최단거리로 이동했을 때, 도착할 수 있어야 한다는 조건입니다.
시간복잡도
놀랍게도 각 다음 장소로 O(1)만에 이동할 수 있습니다.
이를 K번 반복하므로 시간복잡도는
O(K)
입니다.
소스코드
#include <string> #include <vector> using namespace std; int n, m, r, c, k; int dx[] = {1, 0, 0, -1}, dy[] = {0, -1, 1, 0}; string ds = "dlru", s; bool isPsb(int x, int y) { return x > 0 && x <= n && y > 0 && y <= m && k >= abs(x-r) + abs(y-c); } string solution(int tn, int tm, int x, int y, int tr, int tc, int tk) { n = tn, m = tm, r = tr, c = tc, k = tk; while (k--) { bool isGo = false; for (int i=0; i<4; i++) { int nx = x+dx[i], ny = y+dy[i]; if (!isPsb(nx, ny)) continue; x = nx, y = ny, s += ds[i]; isGo = true; break; } if (!isGo && k == 0) return "impossible"; } return s; }
1, 2, 3 떨어뜨리기 - Lv. 4
해설
자식노드로의 이동경로를 작은 숫자를 가진애부터 큰애로 이동하며 순환시킵니다.
저는 인접리스트를 사용해서 자식노드들을 정렬해둔 후,
각 노드마다 idx배열을 만들어 이동할 때마다 idx를 증가시켰습니다.
idx가 마지막에 도달했을 때는 0으로 옮깁니다.
이제 리프노드로 떨어뜨리는 과정을 보면,
리프노드로 떨어지는 순서들은 이미 고정되어 있습니다.
그리고 떨어지는 숫자들을 최소로 해야하므로 숫자를 3으로 가정하고
하나씩 노드를 떨어뜨리며 정답을 낼 수 있는지 검사해야합니다.
숫자를 떨어뜨리며 검사해야하는 경우는 3가지가 있습니다.
A. 당장 정답을 낼 수 있음.
B. 당장은 정답을 낼 수 없지만 가능성이 남아있는 경우
C. 절대 정답을 낼 가능성조차 없는 경우
인데, 각 과정을 살펴보면
A번은 모든 노드의 떨어뜨린 모든 숫자를 3으로 가정했을 때,
노드의 숫자 합이 target[node]보다 크고, 이를 모든 노드가 만족해야합니다.
이때는 정답을 낼 수 있으므로, 다음 과정으로 넘어가면 됩니다.
B번은 어떤 노드의 떨어뜨린 모든 숫자를 3으로 가정했음에도
target[node] 미만이 되는 경우가 존재하는 경우입니다.
이때는 더 숫자를 부여해서 target[node] 이상으로 만들 수 있으므로
아직 가능성이 남아있기 때문에 숫자를 더 부여하면서 관찰해보아야합니다.
C번은 어떤 노드에 떨어뜨려진 모든 숫자를
1로 가정했음에도 target[node]보다 큰 경우입니다.
이 경우에는 정답을 낼 수 있는 가능성조차 없습니다.
{-1}을 반환해서 알고리즘을 종료합시다.
이제 A번 이후의 과정을 살펴봅시다.
가장 사전순으로 앞서는 답이 되어야하므로
먼저 떨어뜨리는 숫자부터 1부터 3까지 부여하면서
각각의 숫자를 부여함에도 나머지 숫자를 3으로 가정했을 때, 남은 횟수만으로
target[node] - 현재숫자 이상이 만족되면 됩니다.
모든 숫자를 부여했다면 정답을 반환하면 됩니다.
시간복잡도
숫자를 떨어뜨리는 과정은 최대 O(N)까지 소요될 수 있습니다.
떨어뜨리고 정답가능성을 확인하는 과정은 O(N) 입니다.
그리고 정답 가능성과 떨어뜨리는 과정은 최대 T/3*N까지 반복될 수 있습니다.
(T: target의 원소 크기)
그리고 떨어뜨리는 숫자는 최대 T/3N개이므로
이를 T/3N개를 모두 확인하며 숫자를 부여합니다.
모두 고려해보면
O(T/3N(N+N) + T/3*N)
= O(N^2 * T)
입니다.
최악의 경우는
N = 101, T = 100이므로
백만 정도가 나와서 충분히 시간안에 해결됩니다.
소스코드
#include <string> #include <vector> #include <algorithm> #include <iostream> using namespace std; vector<int> tree[101], cnts(101), order, ans; int idx[101]; int n; void dropCnt(int node) { // is Leaf Node (base case) if (tree[node].empty()) { cnts[node]++; order.push_back(node); return; } // is Internal Node (recusion case) dropCnt(tree[node][idx[node]++]); // if child node is last node if (idx[node] == tree[node].size()) idx[node] = 0; } int isPsb(const vector<int>& target) { for (int i=1; i<=n; i++) { // Can't make answer if (cnts[i] > target[i-1]) return -1; // yet impossible if (cnts[i]*3 < target[i-1]) return 0; } // possible return 1; } vector<int> solution(vector<vector<int>> edges, vector<int> target) { // making Tree for (auto v: edges) { tree[v[0]].push_back(v[1]); n = max(n, max(v[0], v[1])); } for (auto& v: tree) sort(v.begin(), v.end()); // checking Possibility while (true) { int isPossible = isPsb(target); // Can't make answer if (isPossible == -1) return {-1}; // isPossible if (isPossible == 1) break; // yet impossible dropCnt(1); } // determine Number for (int i=0; i<order.size(); i++) { int node = order[i]; int& cnt = cnts[node]; for (int j=1; j<=3; j++) { if ((cnt-1)*3 >= target[node-1]-j) { ans.push_back(j); cnt -= 1; target[node-1] -= j; break; } } } return ans; }