문자열을 압축시켜 가장 적은 길이로 만드는 문제이다. 예를 들어 abababab를 2개씩 압축하면 4ab가 되고, 4개씩 압축하면 2abab가 된다. 그 외 길이로는 압축불가능이다. 굳이 따지면 8개씩 1abababab가 가능하긴 할텐데 이러면 길이가 늘어나서 할 이유가 없다. 아무튼 그래서 최소 길이는 3이다.
압축을 중간중간 여러 번 할 수도 있는데, ababcdababef같은 경우 길이 2로 압축시켜서, 2abcd2abef 이렇게 압축시킬 수 있고 이게 최선이다.
항상 앞에서부터 같은 길이씩으로만 끊을 수 있는데, xabababab같은 경우 x4ab 이렇게는 못 끊고, xa/ba/ba/ba/b 이렇게 끊겨서 xa3bab로는 만들 수 있다.
압축할 수 있는 경우, 항상 압축을 하는 것이 최소 본전이거나 더 이득이다.
문자열 길이가 최대 1000이므로, 그냥 각 길이마다 다 비교하면서 작성하는 $O(n^2)$풀이도 시간초과가 나지 않는다.
길이 1로 압축해보고, 2로 압축해보고, ..., s.size() / 2로 압축해보고.. 를 반복하면 된다.
문자열 해싱을 사용한다면 길이가 100만 정도일 때도 1초 안쪽으로 구할 수 있다.
#include <string>
#include <vector>
using namespace std;
int intlen(int n) {
int ret = 0;
while (n) {
ret++;
n /= 10;
}
return ret;
}
int solution(string s) {
int ans = s.size();
for (int len = 1; len <= s.size() / 2; ++len) {
int now = len + s.size() % len, con = 0;
for (int i = 1; i < s.size() / len; ++i) {
bool b = 1;
for (int j = i * len; j < (i + 1) * len; ++j) {
if (s[j] != s[j - len]) {
b = 0;
break;
}
}
if (b) con++;
else {
if (con) {
now += intlen(con + 1);
con = 0;
}
now += len;
}
}
if (con) now += intlen(con + 1);
ans = min(ans, now);
}
return ans;
}
2번. 올바른 괄호 문자열
균형잡힌 괄호 문자열을 올바른 괄호 문자열로 바꾸는 문제이다.
문제 지문에 어떤 알고리즘을 쓰면 되는지 친절히 나와있는데, 그대로 구현하면 된다.
재귀함수로 구현하면 복잡도가 $O(n^2)$인데, 마찬가지로 n = 1000이라 문제없다.
#include <string>
#include <vector>
using namespace std;
string solution(string p) {
if (p.size() == 0) return "";
int a = 0, b = 0;
for (int i = 0; i < p.size(); i += 2) {
if (p[i] == '(') a++;
else b++;
if (p[i + 1] == '(') a++;
else b++;
if (a == b) {
int cnt = 0;
bool bal = 1;
for (int j = 0; j < i + 2; ++j) {
if (p[j] == '(') cnt++;
else cnt--;
if (cnt < 0) bal = 0;
}
if (bal) {
return p.substr(0, i + 2) + solution(p.substr(i + 2, p.size() - i - 2));
}
else {
string ret = "(";
ret += solution(p.substr(i + 2, p.size() - i - 2));
ret += ')';
for (int j = 1; j < i + 1; ++j) {
if (p[j] == '(') ret += ')';
else ret += '(';
}
return ret;
}
}
}
}
3번. 열쇠랑 자물쇠 문제
(n이 20이었는지 40이었는지가 잘 기억이 안 나서 40이라고 가정하고 쓴다)
이런 문제는 시간 복잡도를 잘 따져보아야 하는데,
회전할 수 있는 경우의 수가 4이고 체크해야 할 자물쇠의 위치는 $(n+m-1)^2$개, 한 번 체크할 때마다 $m^2$번 체크해야 하므로 연산 횟수는 최대 $4 \times 40^2 \times 80^2$으로 4000만 정도이다.
대략 수백ms 정도에 돌아갈 정도이므로 다 체크해보면 된다.
#include <string>
#include <vector>
using namespace std;
bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
int m = key.size(), n = lock.size();
int keyr[4][20][20];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < m; ++j) {
keyr[0][i][j] = key[i][j];
}
}
for (int r = 1; r < 4; ++r) {
for (int i = 0; i < m; ++i) {
for (int j = 0; j < m; ++j) {
keyr[r][i][j] = keyr[r - 1][m - 1 - j][i];
}
}
}
int hom = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (lock[i][j] == 0) hom++;
}
}
for (int i = -m + 1; i < n; ++i) {
for (int j = -m + 1; j < n; ++j) {
int nowhom = 0;
for (int ii = 0; ii < m; ++ii) {
if (i + ii < 0 || i + ii >= n) continue;
for (int jj = 0; jj < m; ++jj) {
if (j + jj < 0 || j + jj >= n) continue;
if (lock[i + ii][j + jj] == 0) nowhom++;
}
}
if (nowhom != hom) continue;
for (int r = 0; r < 4; ++r) {
for (int ii = 0; ii < m; ++ii) {
if (i + ii < 0 || i + ii >= n) continue;
for (int jj = 0; jj < m; ++jj) {
if (j + jj < 0 || j + jj >= n) continue;
if (keyr[r][ii][jj] + lock[i + ii][j + jj] != 1) {
goto next;
}
}
}
return 1;
next:;
}
}
}
return 0;
}
4번. 가사와 쿼리 문제
이게 나름 고인물 문제인 것 같다. 트라이라는 자료구조를 사용한다면 정확성과 효율성 둘 다 만족시킬 수 있다.
물음표는 prefix로 붙거나 suffix로 붙거나 둘 중 하나이므로 일반 word로 트라이를 만들고, 모든 word를 reverse해서 트라이를 만든 후
??abc 꼴의 쿼리는 reverse된 word로 만든 트라이에서, abc?? 꼴의 쿼리는 그냥 트라이에서 갯수를 찾으면 된다.
구현하는 데에서 차이가 있긴 하겠지만, 내 생각에 길이별로 트라이를 따로 만드는 게 편할 것 같다.
#include <string>
#include <vector>
#include <memory.h>
using namespace std;
int trie[2020010][26];
int cnt[2020010];
int index;
vector<int> solution(vector<string> words, vector<string> queries) {
memset(trie, 0, sizeof(trie));
memset(cnt, 0, sizeof(cnt));
index = 20001;
for (string& s: words) {
int len = s.size();
int now = len;
for (int i = 0; i < len; ++i) {
cnt[now]++;
if (trie[now][s[i] - 'a'] == 0) {
trie[now][s[i] - 'a'] = index;
now = index++;
}
else {
now = trie[now][s[i] - 'a'];
}
}
now = 10000 + len;
for (int i = len - 1; i >= 0; --i) {
cnt[now]++;
if (trie[now][s[i] - 'a'] == 0) {
trie[now][s[i] - 'a'] = index;
now = index++;
}
else {
now = trie[now][s[i] - 'a'];
}
}
}
vector<int> ans;
for (string& s: queries) {
int len = s.size();
if (s[0] == '?') {
int now = 10000 + len;
for (int i = len - 1; i >= 0; --i) {
if (s[i] == '?') {
ans.push_back(cnt[now]);
break;
}
if (trie[now][s[i] - 'a'] == 0) {
ans.push_back(0);
break;
}
now = trie[now][s[i] - 'a'];
}
}
else {
int now = len;
for (int i = 0; i < len; ++i) {
if (s[i] == '?') {
ans.push_back(cnt[now]);
break;
}
if (trie[now][s[i] - 'a'] == 0) {
ans.push_back(0);
break;
}
now = trie[now][s[i] - 'a'];
}
}
}
return ans;
}
5번. 다리 건설하는 문제(?)
안 풀어서 정확히는 모르는데 구현문제이다. 그냥 하라는대로 구현하면 된다.
6번. 원형 벽에서 친구들이 출격해서 틈새를 매우는 문제
문제를 풀기에 앞서 몇 가지를 관찰하자.
먼저, 이동가능거리가 적은 친구랑 많은 친구 중에는 많은 친구를 사용하는 것이 무조건 이득이다.
또 시작점은 틈새가 있는 점만 따져보아도 충분하다.
이제 문제를 풀어보자. 이것도 모든 경우를 다 해볼 수 있을까?
경우의 수를 세어보면 최대 $_{15}P_8$이 되는데, 2.5억 정도이다.
시간제한이 안 써있어서 잘 몰랐는데 시간제한이 아마 10초였나보다. 즉, 구현만 잘 한다면 충분히 시간내에 돌아간다.
조금 더 빠른 방법은 없을까?
이 문제는 같은 subproblem을 여러 번 풀기 때문에, dp를 사용한다면 더 빠른 시간 내에 풀 수 있다.
dp[사용한 친구 수][cover되지 않은 애들을 bitmask로 표시]로 두고 푼다면 26만 개 정도의 state만 나온다.
아래 코드는 그냥 다 해보는 버전이다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int ans = 9;
bool covered[15];
vector<int> cov;
void solve(int d, int n, vector<int>& weak, vector<int>& dist) {
bool allCovered = 1;
for (int i = 0; i < weak.size(); ++i) {
if (!covered[i]) {
allCovered = 0;
break;
}
}
if (allCovered) {
ans = min(ans, d);
return;
}
if (d == dist.size()) {
return;
}
for (int i = 0; i < weak.size(); ++i) {
if (!covered[i]) {
int cnt = 0;
for (int j = 0; j < weak.size(); ++j) {
if (covered[j]) continue;
int dd = weak[j] - weak[i];
if (dd < 0) dd += n;
if (dd <= dist[d]) {
covered[j] = 1;
cov.push_back(j);
cnt++;
}
}
solve(d + 1, n, weak, dist);
while (cnt--) {
covered[cov.back()] = 0;
cov.pop_back();
}
}
}
}
int solution(int n, vector<int> weak, vector<int> dist) {
for (int i = 0; i < 15; ++i) covered[i] = 0;
ans = 9;
sort(dist.rbegin(), dist.rend());
solve(0, n, weak, dist);
if (ans == 9) return -1;
else return ans;
}
7번. 로봇청소기 문제
간단한 BFS 문제. 로봇이 가로 방향으로 있는 경우와 세로 방향으로 있는 경우 둘 다 표시해가면서, BFS만 하면 충분하다.
안타깝게 풀다가 시간 종료...
5번, 7번 문제와 6번 dp를 이용한 풀이는 추후에 문제가 올라오면 코드를 추가해야겠다.
