2022 카카오 여름인턴십 코딩테스트

정확히 90분 걸려서 풀었는데, 코테 왜이리 어려워졌을까

1- 성격 유형 검사하기 (0:04)

solved.ac 기준 체감 난이도 - 실버 3

열심히 구현해주자. $1$번치고 좀 더 쉬운편

map<char, int> idx{
   {'R', 0},
   {'T', 1},
   {'C', 2},
   {'F', 3},
   {'J', 4},
   {'M', 5},
   {'A', 6},
   {'N', 7},
};

string solution(vector<string> survey, vector<int> choices) {
   int n = sz(survey);
   vi a(8);

   for (int i = 0; i < n; i++) {
      int c = choices[i];
      string s = survey[i];
      if (c == 1) a[idx[s[0]]] += 3;
      if (c == 2) a[idx[s[0]]] += 2;
      if (c == 3) a[idx[s[0]]] += 1;
      if (c == 5) a[idx[s[1]]] += 1;
      if (c == 6) a[idx[s[1]]] += 2;
      if (c == 7) a[idx[s[1]]] += 3;
   }
   string ret;
   if (a[0] >= a[1]) ret += 'R';
   else ret += 'T';
   if (a[2] >= a[3]) ret += 'C';
   else ret += 'F';
   if (a[4] >= a[5]) ret += 'J';
   else ret += 'M';
   if (a[6] >= a[7]) ret += 'A';
   else ret += 'N';
   return ret;
}

2- 두 큐 합 같게 만들기 (0:13)

solved.ac 기준 체감 난이도 - 골드 5

믿음으로 풀면된다.

몇가지 엣지 케이스만 체크해주자.

어차피 정답이 되는 연속된 구간이 있다면 큰곳에서 작은곳으로 옮겨줌으로써 정답이 나오게 된다.

ll solution(vector<int> queue1, vector<int> queue2) {

   int n = sz(queue1);
   ll sum = acc(queue1) + acc(queue2);
   if (sum % 2) return -1;
   if (acc(queue1) == acc(queue2)) return 0;
   ll sum1 = acc(queue1);
   ll sum2 = acc(queue2);

   ll k = sum / 2;
   if (maxe(queue1) > k || maxe(queue2) > k) return -1;

   int ans = 0;
   queue<int> q1, q2;
   for (int i: queue1) q1.push(i);
   for (int i: queue2) q2.push(i);
   while (sum1 != sum2) {
      if (ans > n * 3) return -1;
      if (sum1 > sum2) {
         sum1 -= q1.front();
         sum2 += q1.front();
         q2.push(q1.front());
         q1.pop();
      } else {
         sum2 -= q2.front();
         sum1 += q2.front();
         q1.push(q2.front());
         q2.pop();
      }
      ans++;
   }
   return ans;
}

3- 코딩 테스트 공부 (0:52)

solved.ac 기준 체감 난이도 - 골드 3

함정카드가 있어 멸망했다.

처음에 BFS로 걍 생각없이 하다가 안되는거알고 반복문 dp로 돌리다가 반복문 dp가 아닌 재귀로 짜야하는걸 깨닫느라 시간도 오래걸렸다.

게다가 또 말린 부분은 왜 자꾸 MAX 제한을 더 크게줘야 테케가 통과하지를 생각해보니 (150, 1) 같이 보상이 주어지고 뒤에 1을 계속 써야하는 경우에 (150) 이 계속 증가해서 올바른 값을 구해주지 않는다는 것이였다.

따라서 $a, c$가 있을 때, 계속 최대값을 넘어간다면 최대값으로 제한해주는 테크닉이 필요했고, 이 문제들 중에서 가장 배울게 있었던 문제이다.

그리고 이 문제에 효율성이 시간제한이 뭔가 왜 안돌지 하게 걸려있기도 한데, 프로그래머스에서 문제를 만들어본 입장에서 시간을 제한하는게 아니라 샘플 코드의 배수로 시간을 제한하다보니 불편한점이 있어 그럴것같기도 하다.

const int MAX = 190;
int solution(int alp, int cop, vector<vector<int>> problems) {
   problems.pb({0, 0, 1, 0, 1});
   problems.pb({0, 0, 0, 1, 1});
   int a_req_mx = 0, c_req_mx = 0;
   for (const auto &to: problems) {
      int a_req = to[0], c_req = to[1], a_rwd = to[2], c_rwd = to[3], cost = to[4];

      a_req_mx = max(a_req_mx, a_req);
      c_req_mx = max(c_req_mx, c_req);
   }

   vvi dp(MAX + 1, vi(MAX + 1, -1));
   function<int(int, int)> fn = [&](int a, int c) -> int {
      a = min(a, MAX);
      c = min(c, MAX);
      if (a >= a_req_mx && c >= c_req_mx) return 0;
      int &ret = dp[a][c];
      if (~ret) return ret;
      ret = 1e9;
      for (const auto &to: problems) {
         int a_req = to[0], c_req = to[1], a_rwd = to[2], c_rwd = to[3], cost = to[4];
         if (a_rwd == 0 && c_rwd == 0) continue;
         if (a_req > a || c_req > c) continue;
         ret = min(ret, cost + fn(a + a_rwd, c + c_rwd));
      }
      return ret;
   };
   int ret = fn(alp, cop);
   assert(ret != 1e9);
   return ret;
}

4- 등산코스 정하기 (1:07)

solved.ac 기준 체감 난이도 - 골드 2

그냥 정상들부터 BFS를 돌려서 각 값들을 <지나온 간선의 최소 가중치, 정상인 시작점> pair의 최소값으로 계속 갱신해주면 답이 바로 구해진다.

vector<int> solution(int n, vector<vector<int>> paths, vector<int> starts, vector<int> tops) {
   vector<vector<pi>> edges(n);
   for (auto &v: paths) {
      v[0]--;
      v[1]--;
      edges[v[0]].pb({v[1], v[2]});
      edges[v[1]].pb({v[0], v[2]});
   }
   for (int &i: starts)i--;
   for (int &i: tops)i--;
   vector<pi> dp(n, {1e9, 1e9});
   queue<int> q;
   for (int t: tops) {
      dp[t] = {0, t};
      q.push(t);
   }
   while (sz(q)) {
      int cur = q.front();
      q.pop();
      for (auto &[to, w]: edges[cur]) {
         int nxt_w = max(dp[cur].fi, w);
         pi nxt = {nxt_w, dp[cur].se};
         if (dp[to] > nxt) {
            dp[to] = nxt;
            q.push(to);
         }
      }
   }
   int min_w = 1e9;
   for (int s: starts) {
      min_w = min(min_w, dp[s].fi);
   }
   int ans = 1e9;
   for (int s: starts) {
      if (dp[s].fi == min_w) {
         ans = min(ans, dp[s].se + 1);
      }
   }

   return {ans, min_w};
}

5- 행렬과 연산 (1:30)

solved.ac 기준 체감 난이도 - 플레티넘 5

풀이는 금방 떠올렸는데, 구현이 좀 걸렸다.

shift는 y offset을 변경해주는 것으로 처리하고, 회전은 좀 까다롭다.

모든걸 deque 로 바꾼 다음에, $0,~X-1$ 번 column은 따로 처리해줘야한다.

네개의 덱을 회전시키는듯하게 구현하면 된다.

오프셋 관리도 좀 헷갈리는데, 쉬프트될때마다 각 가로줄의 맨 왼쪽 오른쪽친구들도 바꿔줌을 잊지말자.

여기서 좀 헤맸다.

vector<vector<int>> solution(vector<vector<int>> original, vector<string> op) {
   int Y = sz(original), X = sz(original[0]);
   int y_offset = 0;
   vector<deque<int>> b(Y);

   deque<int> col1, col2;
   for (int y = 0; y < Y; y++) for (int i: original[y]) b[y].pb(i);
   for (int y = 0; y < Y; y++) {
      col1.pb(original[y][0]);
      col2.pb(original[y][X - 1]);
   }

   for (string o: op) {
      if (o[0] == 'R') {
         int y1 = y_offset;
         int y2 = md(Y, y_offset - 1);
         b[y1][0] = col1[0];
         b[y1][X - 1] = col2[0];
         b[y2][0] = col1[Y - 1];
         b[y2][X - 1] = col2[Y - 1];

         col1.pop_front();
         b[y1].push_front(col1.front());

         b[y1].pop_back();
         col2.push_front(b[y1].back());

         col2.pop_back();
         b[y2].push_back(col2.back());

         b[y2].pop_front();
         col1.push_back(b[y2].front());
      } else {
         y_offset = md(Y, y_offset - 1);
         int y1 = y_offset;
         int y2 = md(Y, y_offset - 1);


         col1.push_front(col1.back());
         col1.pop_back();
         col2.push_front(col2.back());
         col2.pop_back();
      }
   }

   vvi ans(Y, vi(X));
   for (int y = 0; y < Y; y++) {
      for (int x = 0; x < X; x++) {
         if (x == 0) {
            ans[y][x] = col1[y];
         } else if (x == X - 1) {
            ans[y][x] = col2[y];
         } else {
            int yy = md(Y, y + y_offset);
            ans[y][x] = b[yy][x];
         }
      }
   }
   return ans;
}