2019년 9월 7일에 2020 KAKAO BLIND RECRUITMENT 1차 코딩 테스트가 있었다. 직접 접수를 해서 풀어본 것이 아니라서 onsite인 2차는 풀 수가 없다는 점이 아쉽다.
각 문제에 대한 간단한 설명과 풀이를 작성했다.
문제1.
문자열이 주어졌을 때, 해당 문자열을 특정 단위로 잘라서 런 렝스 부호화(Run-length encoding)을 수행했을 때, 가장 짧은 경우의 길이를 반환하는 문제다.
예를 들어서 다음의 문자열에 대해 생각해 보자.
abcabcabcabcdededededede
이 문자열을 단위별로 자른 결과는 다음과 같다.
- 2개 단위:
abcabcabcabc6de - 3개 단위:
4abcdededededede - 4개 단위:
abcabcabcabc3dede - 6개 단위:
2abcabc2dedede
6개 단위로 자른 경우 길이가 14로 가장 짧다. 따라서 답은 14이다.
풀이
입력되는 문자열의 길이가 짧기 때문에 자르는 단위 길이를 1부터 시작하여 늘려 가면서 이웃한 단위 길이 문자열과 최대 얼마나 일치하는지 판단한다.
첫 번째 문자 부터 단위 길이만큼 자르기 때문에 탐색중인 단위 문자열에서 최대로 압축시키는 경우만 고려해주면 된다. 만약 동일한 문자열이 2번 이상 등장하는 경우, 표기할 숫자의 자릿수까지 고려하여 문자열의 길이를 계산한다.
문제2.
균형잡힌 괄호 문자열이 주어졌을 때, 문제에서 주어진 알고리즘을 수행하여 올바른 괄호 문자열로 변형하여 반환하는 문제다.
문제에서 설명한 균형잡힌 괄호 문자열과 올바른 괄호 문자열은 다음과 같다.
균형잡힌 괄호 문자열: ‘(‘와 ‘)’로만 이루어진 문자열이 있을 경우, ‘(‘의 개수와 ‘)’의 개수가 같다면 이를균형잡힌 괄호 문자열이라 부른다.올바른 괄호 문자열:균형잡힌 괄호 문자열에 대해 ‘(‘와 ‘)’의 괄호의 짝도 모두 맞을 경우에는 이를올바른 괄호 문자열이라고 부른다.
그리고 문제에서 주어진 알고리즘은 다음과 같다.
- 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다
- 문자열 w를 “두 균형잡힌 괄호 문자열” u, v로 분리합니다. 단, u는 균형잡힌 괄호 문자열로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
- 문자열 u가 “올바른 괄호 문자열” 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
- 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
- 문자열 u가 “올바른 괄호 문자열”이 아니라면 아래 과정을 수행합니다.
- 빈 문자열에 첫 번째 문자로 ‘(‘를 붙입니다.
- 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
- ’)’를 다시 붙 입니다.
- u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
- 생성된 문자열을 반환합니다.
풀이
문제에서 구현해야 할 알고리즘을 설명하고 있다. 문제에 나와있는 대로 알고리즘을 구현하면 해결된다.
2번 단계에서 더 이상 분리할 수 없어야 한다는 조건이 있다. 이는 u에서 맨 오른쪽 문자들을 제거하여 균형잡힌 문자열로 만들 수 없어야 한다는 것이다. 따라서 주어진 문자열을 왼쪽 부터 탐색했을 때, 최초로 균형잡힌 문자열이 되는 경우까지를 문자열 u라고 할 수 있다. 이는 최초로 ‘(‘의 개수와 ‘)’개수가 같아지는 경우와 같다. (단, 1개 이상 있는 경우)
나머지 연산 과정은 재귀함수를 이용하여 주어진 대로 구현만 하면 된다.
문제3.
자물쇠를 나타내는 2차원 배열과 열쇠를 나타내는 2차원 배열이 각각 주어진다. 이들의 형태는 다음과 같이 주어진다.
잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다.
자물쇠와 열쇠는 홈과 돌기로 이루어져 있다. 배열에서 0은 홈을, 1은 돌기를 나타낸다.
자물쇠를 풀기 위해서는 자물쇠의 모든 홈을 열쇠의 돌기로 채워야 한다. 이때 자물쇠의 돌기와 열쇠의 돌기가 만나서는 안되며, 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않는다.
열쇠는 90도 단위로 회전시킬 수 있다.
열쇠와 자물쇠를 나타내는 두 개의 배열이 주어졌을 때, 열쇠로 자물쇠를 열 수 있으면 true를, 열 수 없으면 false를 반환하는 함수를 구현해야 하는 문제다.
풀이
열쇠를 회전시킬 수 있으므로, 주어진 2차원 배열을 90도 회전시키는 함수를 구현해야 한다.
배열을 90도 회전시키는 방법에는 여러가지가 있을 수 있다. 여기서 사용한 방법은 각 배열의 원소를 회전시킨 후의 위치로 이동시키는 것이다. 2차원 배열의 4개 면에 대해 각각 계산해주는 과정을 구현하면 회전연산을 구현할 수 있다. 크기가 M x M인 2차원 배열 K를 Counter clock wise로 90도 회전은 다음과 같이 구현할 수 있다.
void rotatekey(){
bool tmp[MAXN][MAXN];
for(int y = 0; y < M; y++){
for(int x = 0; x < M; x++){
tmp[y][x] = K[y][x];
}
}
for(int j = 0; j < M / 2; j++){
int x = j, y = j;
int x_ = M - j - 1, y_ = j;
for(int d = 0; d < M - 2 * j; d++){
K[y][x] = tmp[y_][x_];
x++;
y_++;
}
}
for(int j = 0; j < M / 2; j++){
int x = M - j - 1, y = j;
int x_ = M - j - 1, y_ = M - j - 1;
for(int d = 0; d < M - 2 * j; d++){
K[y][x] = tmp[y_][x_];
y++;
x_--;
}
}
for(int j = 0; j < M / 2; j++){
int x = M - j - 1, y = M - j - 1;
int x_ = j, y_ = M - j - 1;
for(int d = 0; d < M - 2 * j; d++){
K[y][x] = tmp[y_][x_];
x--;
y_--;
}
}
for(int j = 0; j < M / 2; j++){
int x = j, y = M - j - 1;
int x_ = j, y_ = j;
for(int d = 0; d < M - 2 * j; d++){
K[y][x] = tmp[y_][x_];
y--;
x_++;
}
}
}
이제 현재 열쇠 상태와 자물쇠를 비교하여 열 수 있는지 여부를 판단해야 한다. 자물쇠 배열 위에 열쇠를 올려놓는 방식으로 전체 탐색하는 방법을 생각할 수 있다. 열쇠는 자물쇠의 영역 밖에 존재할 수 있으므로 자물쇠와 걸치는 위치에 열쇠를 올려놓는 경우도 고려하여 구현해야 한다. 이후 열쇠의 홈과 자물쇠의 홈이 만나는 경우가 없는지, 자물쇠의 홈을 열쇠의 키가 모두 채우는지 여부를 판단한다.
자물쇠의 모든 홈을 채워야 하므로, 자물쇠에 존재하는 모든 홈의 개수와 현재 탐색중인 상태에서 채운 홈의 개수를 비교하는 과정도 필요하다.
이후 4번 회전하며 각각의 경우에 대해 열 수 있는지 여부를 판단하면 해결할 수 있다.
문제4.
단어들이 담겨 있는 words배열과 찾고자 하는 키워드가 담긴 queries배열이 주어진다. queries배열에는 와일드카드 문자 ‘?’가 포함되어 있다. 와일드카드 문자는 어떤 문자에도 매치된다.
두 문자열이 매치되기 위해서는 와일드 카드를 제외한 모든 문자가 같아야 하고, 두 문자열의 길이도 같아야 한다.
예를 들어, fro??은 frodo, front, frost 등에 매치되지만 frame, frozen에는 매치되지 않는 식이다.
이때 queries의 각 키워드 별로 매치된 단어가 몇 개인지 순서대로 배열에 담아 반환하는 함수를 구현해야 한다.
풀이
이 문제는 효율성 테스트에서 부분 점수가 있는 문제다. 즉, 단순 구현하는 것보다 더 효율적인 방법을 생각해야 한다.
단순히 구현하는 방법은 각 검색 키워드에 대해 동일한 길이의 문자열을 찾아 비교하여 매치 여부를 판단하면 된다.
이것을 더 빠르게 처리할 수는 없을까?
문자열 검색을 처리하는 자료구조 중, Trie 자료구조를 활용할 수 있다.
Trie자료구조를 활용하면 모든 words를 검색하지 않고도 빠르게 찾을 수 있다. 주어진 키워드의 길이가 Trie로 처리할 수 있는 정도의 크기이므로 Trie자료구조에 와일드카드만 적절히 처리해 주면 효율성까지 해결할 수 있을 것이다.
문제5.
기둥과 보를 주어진 위치에 설치 또는 제거하는 쿼리가 주어졌을 때, 모든 쿼리를 처리한 뒤의 설치 상태를 반환하는 문제다.
설치는 2차원 가상 벽면에 하며, 기둥과 보는 길이가 1인 선분으로 표현된다. 이때, 다음과 같은 규칙을 가지고 있다.
- 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 한다.
- 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 한다.
단, 바닥은 벽면의 맨 아래 지면을 말한다.
한 쿼리에 대해 해당 쿼리를 실행하고 난 뒤의 상태가 규칙을 어긋난다면, 해당 쿼리는 무시한다.
풀이
주어진 벽면의 크기가 최대 100 x 100으로 매우 작으므로 전체탐색만으로 해결할 수 있다.
따라서 규칙을 만족하는지에 대한 여부를 판단하는 함수를 구현하여 각 쿼리를 수행할지를 판단하는 방법으로 구현할 수 있다.
이때, 판단 함수를 설치된 구조물에 대해서만 탐색하면서 2차원 배열을 활용해 필요한 위치만 참조하면 빠르게 해결할 수 있다.
문제6.
완전히 동그란 모양의 n미터 길이의 레스토랑 외벽이 있다. 외벽에는 취약한 지점들이 있고, 해당 취약 지점들이 손상되었는지 친구들을 보내 확인해야 한다.
각 친구들은 이동할 수 있는 거리가 정해져 있고 외벽을 따라 시계방향 또는 반시계방향으로 이동할 수 있다. 각 친구를 외벽의 한 지점에서 출발시킬 때, 모든 취약 지점들을 점검할 수 있는 경우의 최소 인원은 몇명인지 구하는 문제다.
위치는 12시 방향을 0으로 하고 시계방향으로 증가한다.
친구들을 모두 투입해도 취약 지점을 전부 점검할 수 없는 경우에는 -1을 반환해야 한다.
풀이
어떤 지점에서 출발해야 가장 많은 취약 지점을 포함할 수 있을까?
아마 도착 지점이 취약지점인 경우일 것이다. 이를 반대로 생각해 보면, 시작 지점이 취약지점인 경우 가장 많은 취약 지점을 포함할 수 있다는 것이다.
따라서 각 친구의 출발 지점은 취약지점의 위치가 된다.
탐색하는 사람의 수를 최소화할 때, 이동할 수 있는 거리가 가장 긴 사람이 가장 많은 취약 지점을 해결할 수 있으므로 탐색 가능한 거리가 가장 긴 사람부터 해결해 나가야 한다.
취약 지점의 개수는 15개 이하로 매우 작으므로, 다음과 같은 배열을 이용할 수 있다.
C[i][j] := i번째 친구가 j번째 취약지점 부터 이동했을 때, 점검할 수 있는 취약지점들의 집합
이때, i번째는 탐색 가능한 거리를 기준으로 한다.
이제 dp[i][j]를 결정할 때, 다음과 같은 전략을 활용할 수 있다.
dp[i][j] := max(n(C[i - 1][k] ∪ C[i][j]))
dp값이 취약 지점의 개수가 되는 최소 i값이 답이된다.
모든 사람을 탐색했는데도 dp값이 취약 지점의 개수보다 작다면 모든 친구를 투입해도 모든 취약 지점을 점검할 수 없는 경우이므로, -1을 반환한다.
문제7.
N x N 크기의 지도에서 2 x 1 크기인 로봇을 움직여서 (N, N) 위치까지 이동시켜야 한다.
지도를 나타내는 2차원 배열의 가장 왼쪽 상단의 좌표를 (1, 1)이라 하고 0은 빈칸을 1은 벽을 나타낸다.
로봇은 처음에 가로상태로 놓여져 있고, 왼쪽의 위치가 (1, 1)인 상태이다. 로봇은 아래, 위, 오른쪽, 왼쪽으로 회전 상태를 유지하며 1칸씩 이동할 수 있고, 회전하여 회전 상태를 바꿀 수 있다. 회전을 할 때에는 회전에 필요한 공간이 모두 빈칸이어야 한다.
이동, 회전을 하는데 각각 1만큼의 시간이 필요할 때, 로봇이 이동할 수 있는 최소 시간을 반환하는 함수를 구현해야 하는 문제다.
풀이
단순히 BFS로 해결할 수 있다. 단지 로봇의 움직임을 조건에 맞추어 처리해 주변 된다.
매 시간 마다 이동, 회전을 수행하도록 움직임을 처리하면 BFS로 해결된다.
후기
대부분 모두 구현이 중점인 문제들이다.
복잡한 구현 문제를 빠르게 풀어내는 능력을 더 요구하는듯 하다.