2023 카카오 블라인드 코딩테스트

최근에 거의 1년만에 다시 취미로 알고리즘을 손에 잡아 골드문제들을 몇개씩 밀어보고 있다.

프로그래머스에서 SQL 문제 풀면서 최근에 카카오가 코딩테스트를 낸게 올라와있길래 나중에 풀어봐야겠다 했는데 한번 풀어보았다.

다푸는데 $3$시간 $20$분정도 걸렸다.

실수도 너무 많았고 그냥 문제 어떻게 푸는지 전혀 감이 안잡힌것도 많다.

PS는 역시 꾸준히해야…

1. 개인정보 수집 유효기간 LV.1 (10 min, AC)

코딩테스트 1번스럽게 문자열을 파싱해서 정보를 취합하는 문제입니다.

문제도 친절하게 한 달이 28일으로 고정시켜놨다고 주어지네요.

$YYYY.mm.dd$ 포맷에서 년 월 일을 이용해 두 날짜간의 차이나는 일수를 계산해주는 함수를 만들어낸다면 쉽게 풀 수 있습니다.

저는 다음과 같이 짜서 활용했습니다.

int diff_day(string dd1, string dd2) {
   int y1 = year(dd1), m1 = month(dd1), d1 = day(dd1);
   int y2 = year(dd2), m2 = month(dd2), d2 = day(dd2);

   if (d1 < d2) {
      d1 += 28;
      m1--;
   }

   int ret = d1 - d2;

   if (m1 < m2) {
      m1 += 12;
      y1--;
   }
   ret += (m1 - m2) * 28;
   ret += (y1 - y2) * 28 * 12;
   return ret;
}

2. 택배 배달과 수거하기 LV.2 (55 min, AC)

갑자기 뇌절와서 이상한 풀이들을 떠올리다가 결국엔 풀었습니다. 시간을 너무 허비했네요..

직관적으로 가장 멀리 있는 집부터 트럭을 갈때도 올때도 꽉꽉 채워서 다녀오는게 항상 유리하다는 것을 파악합니다.

n - 1 부터 0 까지 위치를 이동하며 물류창고에서 가져온 양 go, 회수한 양 from 을 유지하고, 왕복할 필요가 있을 때 다시 왕복하여 정답에 더해주고 이 변수들도 cap 만큼 더해줍니다.

문제의 제한을 자세히 보면 deliveries와 pickups의 크기가 50 이하이고 n이 10^5 이하이기 때문에 O(50n) 정도로 딱히 최적화 없이도 문제가 풀릴 것이라고 예상할 수 있어야 합니다.

구현이 너무 더러워 코드를 첨부하지 못합니다.

다시 깔끔하게 짜서 첨부했습니다.

long long solution(int cap, int n, vector<int> d, vector<int> p) {
   ll ans = 0;
   int go = 0, from = 0;
   for (int i = n - 1; i >= 0; i--) {
      while (d[i] || p[i]) {
         int need = d[i] > go || p[i] > from;
         if (need) {
            go += cap, from += cap;
            ans += 2ll * (i + 1);
         }

         int go_remove = min(go, d[i]);
         go -= go_remove, d[i] -= go_remove;
         int from_remove = min(from, p[i]);
         from -= from_remove, p[i] -= from_remove;
      }
   }

   return ans;
}

3. 이모티콘 할인행사 LV.2 (66 min, AC)

단순한 브루트포스 문제입니다.

가능한 할인율이 4가지 밖에 없고 이상하리만큼 작은 이모티콘의 길이를 보면 브루트포스를 떠올릴 수 있습니다.

최대 $7^4$ 의 경우의 수이기 때문에 매우 작아서 일일히 해보면 됩니다.

vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
   int n = sz(users);
   int m = sz(emoticons);

   vi sales(m);
   vector<pi> ans;
   function<void(int)> fn = [&](int i) -> void {
      if (i == m) {
         int a = 0, b = 0;
         for (int u = 0; u < n; u++) {
            int total = 0;
            for (int e = 0; e < m; e++) {
               if (sales[e] >= users[u][0]) {
                  total += emoticons[e] * (100 - sales[e]) / 100;
               }
            }
            if (total >= users[u][1]) {
               a++;
            } else {
               b += total;
            }
         }
         ans.pb({a, b});
         return;
      }
      for (int s = 10; s <= 40; s += 10) {
         sales[i] = s;
         fn(i + 1);
      }
   };
   fn(0);

   sort(all(ans), greater<>());
   return {ans[0].fi, ans[0].se};
}

4. 표현 가능한 이진트리 LV.3 (112 min, AC)

처음에 문제를 잘못읽고 이 숫자를 만드는 이진트리가 유일한가에 대해서 구하면서 삽질했네요

포화 이진트리의 노드의 개수에 주목합니다.

1, 3, 7, 15, 31 … 처럼 항상 될 수 밖에 없는데, 그럼 이진수에서 루트 노드의 위치도 항상 거기뿐이라는 것을 의미합니다.

적당히 풀기 쉽게 이진수를 문자열로 나타내준다음 뒤집습니다.

즉, 000101 같은 이진수를 101000… 로 만드는 겁니다.

$f(l, r, p)$ 를 p는 바로 위 부모 노드가 1인지의 여부, l 부터 r 까지 $\small (inclusive)$ 에서 1의 개수를 세는 함수라고 한다면,

부모가 0인데 자식들에게 1이 있는 경우들은 이진트리가 불가능한 경우라고 생각할 수 있습니다.

그리고 0001001 같은 이진수인데 루트 노드가 0 번째 1이면 트리의 노드 개수가 1개 뿐이라 제일 큰 1을 포함하지 못하므로 이러한 경우도 그 루트는 정답에서 제외해줘야 합니다.(코드 주석 1)

이렇게 열심히 재귀함수를 짜다보면 정답입니다.

vector<int> solution(vector<long long> numbers) {
   vector<int> answer;

   for (ll n: numbers) {
      string s = bitset<64>(n).to_string();
      int possible = 0;
      reverse(all(s));
      vi root = {0, 1, 3, 7, 15, 31};
      for (int r: root) {
         int can = 1;
         if (s[r] == '0') continue;
         for (int j = r * 2 + 1; j < sz(s); j++) if (s[j] == '1') can = 0;
         if (!can) continue;

         function<int(int, int, int)> fn = [&](int l, int r, int parent) -> int {
            if (l == r) return s[l] == '1';

            int mid = (l + r) >> 1;
            int ret = s[mid] == '1';
            ret += fn(l, mid - 1, s[mid] == '1');
            ret += fn(mid + 1, r, s[mid] == '1');
            if (ret > 0 && s[mid] == '0' || !parent && ret > 0) {
               can = 0;
            }
            return ret;
         };

         fn(0, r * 2, 1);
         if (can) {
            possible = 1;
            break;
         }
      }
      answer.pb(possible);
   }
   return answer;
}

5. 표 병합 LV.3 (142 min, AC)

마치 MERGE 라는 것이 등장할 때부터 분리집합(DSU) 같은 느낌을 풍기지만, 그냥 단순 구현문제입니다.

대략 다음과 같은 구조체를 정의하고 각 셀마다 넣어둡니다.

struct CELL {
   vector<pi> pos;
   string v;

   void add(int y, int x) {
      pos.pb({y, x});
   }
   void remove(int y, int x) {
      pos.erase(find(all(pos), mp(y, x)));
   }
};

...
vector<vector<CELL>> b(50, vector<CELL>(50));
...

여기서 중요한건 어떤 셀 $(r, c)$는 항상 어떤 유일한 CELL 구조체 하나에만 속해있게 관리를 해준다는 점입니다.

예를 들어 merge $a, b$ 를 한다면 $a$에 $b$의 모든 pos들을 옮기고 b의 pos는 clear 시켜준다든지 하는 식입니다.

6. 미로 탈출 명령어 LV.3 (152 min, AC)

그냥 그래프 문제도 아닌 그리디 문제입니다. 처음엔 dddd로 가고 뭐 어떻게 가야하나? 생각이 들었지만

길이 $k$가 정해진 이상 사전순으로 최적을 만들기 위해선 각 순간에 d l r u 순으로 가능한지 불가능한지만 판단해서 최적으로 계속 가주기만 하면 됩니다.

불가능한지 판단하는건 보드 밖으로 나가거나 거기로 이동했을 시에 남은 $k-1$ 번의 횟수 안에 도착점에 도달하지 못하는지만 검사해주면 됩니다.

string solution(int n, int m, int y1, int x1, int y2, int x2, int k) {
   y1--, x1--, y2--, x2--;

   auto can_go = [&](int y, int x, int k) {
      return abs(y2 - y) + abs(x2 - x) <= k;
   };
   auto out = [&](int y, int x) {
      return y < 0 || x < 0 || x >= n || y >= n;
   };

   string ans;
   int y = y1, x = x1;
   while (k) {
      int dy[] = {1, 0, 0, -1}, dx[] = {0, -1, 1, 0};
      bool move = 0;
      for (int d = 0; d < 4; d++) {
         int ny = y + dy[d], nx = x + dx[d];
         if (!out(ny, nx) && can_go(ny, nx, k - 1)) {
            k--, y = ny, x = nx;
            move = 1;
            ans += "dlru"[d];
            break;
         }
      }
      if (!move) return "impossible";
   }

   return ans;
}

7. 1,2,3 떨어뜨리기 LV.4 (201 min, AC)

대망의 하이라이트 문제인데… 제 풀이가 최적인진 모르겠지만 대충 적어보겠습니다.

이 문제에서 주의깊게 봐야할건 제한입니다. 왜이렇게 제한들이 적냐는 말입니다.

최대 노드는 101개 뿐이고 각 target 도 값이 최대 100입니다.

게다가 최대한 완전 이진트리로 펼쳐도 leaf 노드의 수는 $O{\left( \dfrac n2 \right)}$가 되어 대략 $50$개뿐밖에 만들 수 없습니다.

여기서 아이디어를 떠올려보면, 1이든 2든 3이든 뭘 떨어뜨리든 결국 작은 횟수안에 모든 target이 채워져야 한다는 점입니다.

50 * 100 이면 총 target의 합은 5000정도이고 넉넉잡아서 6000회 안에 모든 leaf 노드는 정답이 있다면 항상 채워집니다.

문제에서 노드마다 자식 간선이 계속 변하기 때문에 뭐 정수론적인 접근을 해서 풀어보려고도 했는데,

문제의 제한이 적어서 $O(6000 \cdot 100)$ 정도의 시간복잡도로 6000번 dfs를 돌려보면 그냥 각 시도마다 공이 굴러가는 leaf node를 브루트포스로 구하면 됩니다.

vi child_to(n, 0);
vvi visit_idx(n);
vi fall_idx(6000);

for (int i = 0; i < 6000; i++) {
   function<void(int)> fn = [&](int cur) -> void {
      if (is_leaf[cur]) {
         fall_idx[i] = cur;
         visit_idx[cur].pb(i);
         return;
      }
      int to = edges[cur][child_to[cur]];
      child_to[cur] = (child_to[cur] + 1) % sz(edges[cur]);
      fn(to);
   };
   fn(0);
}

이제 각 시도마다 공이 굴러가는 leaf 노드와 leaf 노드별로 자신이 어떤 인덱스들에 방문되는지 가지고 있는 배열을 얻었습니다.

이제 모든 leaf 노드들에 대해 다음과 같은 것을 얻을겁니다.

시도는 1번째 시도가 0이라고 정의합니다.

$\it \textit{Min}_\textit{end}$ : 자신한테 공이 굴러올 때 3만 떨어뜨린다고 가정하면 제일 먼저 끝나는 시도

$\it \textit{Max}_\textit{end}$ : 자신한테 공이 굴러올 때 1만 떨어뜨린다고 가정하면 최대한 target을 넘지 않고 버틸 수 있는 시도

예를 들어 target이 100인 경우, 자기에게 34번만 공이 굴러오면 끝낼 수 있습니다.

그러면 자신에게 공이 굴러오는 시도들을 저장한 visit_idx[i] 에서 34(인덱스론 33) 번째 시도가 몇번인지를 보면 됩니다.

반대로 target이 100이라면 자기에게 100번을 1을 굴러오게 할때까지 버틸 수 있습니다.

하지만 101번째 공이 굴러오는 시도 - 1 이 최대한 버틸 수 있는 시도가 되어야 합니다.

왜냐면 이미 100이 차도 101이 되기전까진 실패한게 아니기 때문입니다.

vi mn_end(n, 0), mx_end(n, 1e9);
for (int i = 0; i < n; i++) {
   if (is_leaf[i]) {

      int mn_idx = (target[i] + 3 - 1) / 3 - 1;

      if (sz(visit_idx[i]) <= mn_idx)
         return {-1};

      mn_end[i] = visit_idx[i][mn_idx];

      int mx_idx = target[i];

      if (sz(visit_idx[i]) <= mx_idx) {
         // is it right?
      } else {
         mx_end[i] = visit_idx[i][mx_idx] - 1;
      }
   }
}

이제 모든 서로 다른 노드들의 쌍에 대해서 모순이 없는지 검사합니다.

그러니까 어떤 a 노드가 최대로 버틸수 있는 시도 횟수가 100번인데, b 노드가 최소로 끝낼 수 있는 시도 횟수가 150 회라면, a에서 아무리 1만 내려보내면서 질질끌고 b에서 3을 계속 내려봤자 모순이 생겨 정답 배열을 만들 수 없습니다.

for (int i = 0; i < n; i++) {
   for (int j = i + 1; j < n; j++) {
      if (mn_end[i] > mx_end[j] || mn_end[j] > mx_end[i]) {
         return {-1};
      }
   }
}

이제 여기까지 검사했다면 정답의 길이는 mn_end 배열중 가장 큰 값입니다.

왜냐면 정답 배열은 항상 더 짧으면 좋기 때문이고, 각 노드마다 가장 이르게 끝낼 수 있는 횟수들의 최대값이 정답이 되어야 하기 때문입니다.

나머지는 각 노드별로 1을 채울 수 있다면 1을, 2를 채울 수 있다면 2를, 아니면 3을 채워주는 식으로 정답 배열을 구성하면 됩니다.

int dest = maxe(mn_end);

vi ans;
for (int i = 0; i <= dest; i++) {
   int cur = fall_idx[i];

   int remain_visit = max(0, ubi(visit_idx[cur], dest) - lbi(visit_idx[cur], i) - 1);

   assert(target[cur] > 0);
   int can_1 = (target[cur] - 1) <= 3 * remain_visit;

   if (can_1) {
      ans.pb(1);
      target[cur]--;
   } else {
      int can_2 = (target[cur] - 2) <= 3 * remain_visit;
      if (can_2) {
         ans.pb(2);
         target[cur] -= 2;
      } else {
         ans.pb(3);
         target[cur] -= 3;
      }
   }
}

전문

vector<int> solution(vector<vector<int>> input_e, vector<int> target) {
   int n = sz(target);
   vvi edges(n);
   for (auto &v: input_e) {
      edges[v[0] - 1].pb(v[1] - 1);
   }
   for (auto &v: edges)sort(all(v));
   vi is_leaf(n);
   for (int i = 0; i < n; i++) if (sz(edges[i]) == 0) is_leaf[i] = 1;
   for (int i = 0; i < n; i++) {
      if (!is_leaf[i] && target[i]) {
         return {-1};
      }
   }

   vi child_to(n, 0);
   vvi visit_idx(n);
   vi fall_idx(6000);

   for (int i = 0; i < 6000; i++) {
      function<void(int)> fn = [&](int cur) -> void {
         if (is_leaf[cur]) {
            fall_idx[i] = cur;
            visit_idx[cur].pb(i);
            return;
         }
         int to = edges[cur][child_to[cur]];
         child_to[cur] = (child_to[cur] + 1) % sz(edges[cur]);
         fn(to);
      };
      fn(0);
   }

   vi mn_end(n, 0), mx_end(n, 1e9);
   for (int i = 0; i < n; i++) {
      if (is_leaf[i]) {

         int mn_idx = (target[i] + 3 - 1) / 3 - 1;

         if (sz(visit_idx[i]) <= mn_idx)
            return {-1};

         mn_end[i] = visit_idx[i][mn_idx];

         int mx_idx = target[i];

         if (sz(visit_idx[i]) <= mx_idx) {
            // is it right?
         } else {
            mx_end[i] = visit_idx[i][mx_idx] - 1;
         }
      }
   }

   for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
         if (mn_end[i] > mx_end[j] || mn_end[j] > mx_end[i]) {
            return {-1};
         }
      }
   }

   int dest = maxe(mn_end);

   vi ans;
   for (int i = 0; i <= dest; i++) {
      int cur = fall_idx[i];

      int remain_visit = max(0, ubi(visit_idx[cur], dest) - lbi(visit_idx[cur], i) - 1);

      assert(target[cur] > 0);
      int can_1 = (target[cur] - 1) <= 3 * remain_visit;

      if (can_1) {
         ans.pb(1);
         target[cur]--;
      } else {
         int can_2 = (target[cur] - 2) <= 3 * remain_visit;
         if (can_2) {
            ans.pb(2);
            target[cur] -= 2;
         } else {
            ans.pb(3);
            target[cur] -= 3;
         }
      }
   }

   return ans;
}