#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 연습하는 것을 추천한다.
#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를 저장하는 또 다른 인접리스트를 저장하고, 두 번의 다익스트라를 통해 답을 도출해낼 수 있다.
#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;
}
};
