제1회 온코더 공식 코딩테스트 잡담 및 풀이

새로 등장한 코딩테스트 대행 스타트업 사이트다.

문제를 보아하니 그렇게 나쁘지 않은 난이도 및 구성이라 시험을 치뤄봤다. ㅎㅎ 7등이 나온걸 보아 아직 난 멀었나보다 싶다.

[ Solution ]

1. 문자열 변환

  그냥 문제 설명 그대로 해주면 되겠다..

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14

#include <string> using namespace std;    class Solution{ public:     string decryptSpell(string str){         for(int i=2;i<str.length();i+=3){             if('a' <= str[i] && str[i] <= 'z')                 str[i] = str[i] - 'a' + 'A';             else str[i] = '!';         }         return str;     } };

2. 해시 M값 구하기

[ 분류 - Sieve of eratosthenes, Binary search ]

1. 주어진 수식을 이용하여 찾아야하는 소수 범위를 한정한다.

2. 한정된 범위 내의 소수를 탐색한다.

한끗 차이로 7번이나 제출해버렸다. 기준점 찾는 부분에서 등호를 조심하자ㅠ

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

#include <cmath> #include <vector> #include <algorithm> using namespace std; int max_v(int a, int b) { return a > b? a : b; } int min_v(int a, int b) { return a < b ? a : b; } class Solution{ public:     int getHashM(int maxK, int collision) {         int L = maxK / collision, ans = -1, dist = -1, tdist;         long long i, j;         bool chk[20000001] = {1,1};         vector<int> p;         for (i = 2; i < 20000001; i++) {             if (chk[i]) continue;             p.push_back(i);             for (j = i * i; j < 20000001; j += i)                 chk[j] = 1;         }               i = 0;         while (L >= 1 << (i + 1)) i++;         vector<int>::iterator it = lower_bound(p.begin(), p.end(), 1 << i);         while (*it < (1 << (i+1))){             tdist = min_v((1 << (i + 1)) - *it, *it - (1 << i));             if (dist < tdist) {                 ans = *it;                 dist = tdist;             }             it++;         }         return L <= 2 ?  2 : ans;     } };

3. 패킷 줄이기

주어진 내용을 그냥 구현하면 된다. 이 문제가 어렵게 느껴진다면 Encoding/Decoding 관련 문서 또는 bitmasking 연습하는 것을 추천한다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51

#include <string> using namespace std;    class Solution{ public:     int getCode(char c){         if('a' <= c && c <= 'z') return c-'a';         else if('A' <= c && c <= 'Z') return c-'A' + 26;         else if('0' <= c && c <= '9') return c-'0' + 52;         return 62;     }     string to6(int d){         string ret = "";         for(int i=5;i>=0;i--)             ret += (d & (1<<i)) != 0 ? '1' : '0';         return ret;     }           int getHex(string bit4){         int ret = 0, i;         for(i=0;i<4;i++){             ret *= 2;             ret |= (bit4[i]-'0');         }         return ret;     }           char getC(int d){         return d < 10 ? d + '0' : d%10 + 'A';     }           string readOct(string bit8){         string ret = "";         ret += getC(getHex(bit8.substr(0,4)));         ret += getC(getHex(bit8.substr(4,4)));         return ret;     }           string encoder(string message){         string stc = "",ans="";         int i;         for(i=0;i<message.length();i++)             stc += to6(getCode(message[i]));         while (stc.length() % 8 != 0)             stc += '0';         for(i=0;i*8<stc.length();i++){             ans += readOct(stc.substr(i*8,8));         }         return ans;     } };

4. 보급품 수송

[ 분류 - Dijkstra/ Bellman-ford/  Shortest path ]

  모든 정점이 하나의 정점으로 올 때의 최단경로와 다시금 돌아갈 때의 최단 경로를 구해야하는 문제다. 문제에서 주어지듯 방향 그래프이기 때문에 u->v라고 해서 v->u가 되지 않을 수 있다.

  간단하게 생각해보자. u->v의 의미는 정점 u에서 정점 v로 갈 수 있는 간선이 있다는 것이다. 그렇다면 역으로 'v에 도착하기 위해선 u를 거쳐서 올 수 있다.'로 표현을 변경할 수 있다. 따라서 각 도시 정점으로 도착하기 위해서는 어떤 정점을 거쳐야하는 문제로 변형시킬 수 있다. 따라서 정부를 나타내는 정점 k에서 돌아가는 것은 기존 간선을 이용하여 처리할 수 있고, 각 도시 정점에서 정부로 오는 최단 경로는 그래프 G내에 있는 모든 간선 E를 역으로 돌려놓는 것이다. (역방향 간선을 말하는 것은 아님.)

  따라서 u->v라는 데이터 들어온다면 u->v를 저장하는 기존 인접리스트 하나, v->u를 저장하는 또 다른 인접리스트를 저장하고, 두 번의 다익스트라를 통해 답을 도출해낼 수 있다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57

#include <vector> #include <algorithm> #include <queue> #include <cstring> #include <iostream> using namespace std; using ll = long long; int max_v(int a, int b) { return a > b ? a : b; } const int MAX_N = 5000; struct _d { int v, w; }; bool operator<(const _d& a, const _d& b) {     return a.w > b.w; } void dijkstra(int s, vector<vector<_d>>& adj, int dist[MAX_N]) {     dist[s] = 0;     priority_queue<_d> pq;     pq.push(_d{ s,0 });     while (!pq.empty()) {         _d u = pq.top(); pq.pop();         if (dist[u.v] < u.w) continue;         for (_d& v : adj[u.v])             if (dist[v.v] > dist[u.v] + v.w) {                 dist[v.v] = dist[u.v] + v.w;                 pq.push(_d{ v.v, dist[v.v] });             }     } }    class Solution{ public:     int solution(int N, int M, int k, vector<int> A, vector<int> B, vector<int> C) {         vector<vector<_d>> adjf(N), adjr(N);         int i, u, v, w, distf[MAX_N], distr[MAX_N],distt[MAX_N], ans = 0;         for (i = 0; i<M; i++) {             u = A[i], v = B[i], w = C[i];             u--, v--;             adjf[u].push_back(_d{ v,w });             adjr[v].push_back(_d{ u,w });         }         k--;         memset(distf, 0x6F, sizeof distf);         memset(distr, 0x6F, sizeof distr);         dijkstra(k, adjf, distf);         dijkstra(k, adjr, distr);         for (i = 0; i < N; i++)             if (distr[i] == 0x6F6F6F6F) {                 memset(distt, 0x6F, sizeof distt);                 dijkstra(i, adjr, distt);                 distr[i] = distt[k];             }         for (i = 0; i < N; i++) {             if (i == k) continue;             ans = max_v(ans, distf[i] + distr[i]);         }         return ans;     } };