![[코딩테스트] 카카오 인턴십 코딩 테스트 실전 모의고사](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fc9mk6i%2FbtqC1IhOWZu%2F3vWWSsCHCoT04uBfiV3b31%2Fimg.png)
오늘 프로그래머스에서 연 코딩테스트 모의고사를 보았다.
문제는 작년 2019 카카오 인턴십 코딩테스트의 기출문제였다.
슬슬 서류접수 끝나고 코딩테스트 볼 시기도 다가오니 만큼 저번주에 백준에서 봤던 '코딩테스트 대비 모의고사'에 이어 이번주도 코딩테스트 연습이나 할까하고 신청했다.
작년 카카오 인턴십 문제라고 하니 궁금하기도 했고. 사실 작년에 카카오 공채는 지원을 했는데 인턴은 지원자격-기술스택에 해당되는 부분이 거의 없어서 지원을 안했었다. 그래서 문제가 올라오면 풀어야지 하고 있었는데 올라오질 않더라;; 이번 모의고사가 끝나고 다음주, 4월 첫째주에 카카오 테크 블로그에 풀이가 공개된다고 한다.
문제 및 풀이
1번 문제
NxN 크기의 정사각 격자에 인형이 담겨있고, 크레인이 주어진 순서에 따라 인형을 뽑아 바구니에 담는다. 이때, 바구니에 같은 종류의 인형 두개가 연속해서 쌓이면 두 인형이 터지면서 바구니에서 사라진다. 정사각 격자의 상태와 인형을 뽑는 순서가 주어졌을 때 터져서 사라진 인형의 개수를 return하는 문제
풀이
주어진 정사각 격자를 세로줄로 나눠서 하나씩 스택 배열에 담는다.
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 3 |
| 0 | 2 | 5 | 0 | 1 |
| 4 | 2 | 4 | 4 | 2 |
| 3 | 5 | 1 | 3 | 1 |
이렇게 주어지면,
| 0 | 0 | 0 | 0 | 0 | ||||
| 0 | 0 | 1 | 0 | 3 | ||||
| 0 | 2 | 5 | 0 | 1 | ||||
| 4 | 2 | 4 | 4 | 2 | ||||
| 3 | 5 | 1 | 3 | 1 |
이렇게 나눠서 스택에 담는다.
그리고 뽑는 순서에 따라 해당 스택 배열에서 인형을 뽑아 바구니에 담는다.(push) 이때 바구니 맨 위에 담으려는 인형과 맨 위에 있는 인형(top)이 같다면 바구니에서 인형을 뺀다.(pop) 그리고 카운트+2
코드
#include <string>
#include <vector>
using namespace std;
int solution(vector<vector<int>> board, vector<int> moves) {
int answer = 0;
int bSize = board.size();
int mSize = moves.size();
vector<vector<int>> doll; doll.resize(bSize);
vector<int> baguni;
for (int i = 0; i < bSize; i++) {
for (int j = bSize - 1; j >= 0; j--) {
if (board[j][i] == 0) break;
doll[i].push_back(board[j][i]);
}
}
for (int i = 0; i < mSize; i++) {
// 뽑기
int n = moves[i] - 1;
if (doll[n].empty()) continue;
int crane = doll[n].back();
doll[n].pop_back();
// 넣기
if (baguni.empty()) {
baguni.push_back(crane);
}
else {
if (crane == baguni.back()) {
answer += 2;
baguni.pop_back();
}
else {
baguni.push_back(crane);
}
}
}
return answer;
}2번 문제
셀수있는 수량의 순서있는 열거 또는 어떤 순서를 따르는 요소들의 모음을 튜플이라 하고, n개의 요소를 가진 튜플을 n-튜플이라 한다. 튜플은 다음과 같은 성질을 가지고 있다.
- 중복된 원소가 있을 수 있고
- 원소에 정해진 순서가 있으며, 순서가 다르면 다른 튜플이다.
- 튜플의 원소개수는 유한하다.
- 원소의 개수가 유한하고, 중복되는 원소가 없는 튜플이 주어질 때 집합기호 '{', '}'를 통해 표현할 수 있다.
예를 들어 튜플이 (2, 1, 3, 4)인 경우, {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}} 와 같이 표현할 수 있다.
특정 튜플을 표현하는 집합이 담긴 문자열 s가 매개변수로 주어질 때, s가 표현하는 튜플을 배열에 담아 return하는 문제.
풀이
문자열을 분리해서 정수의 형태로 vector에 저장한다.
{{1,2,3},{2,1},{1,2,4,3},{2}}인 경우 [ [1, 2, 3], [2, 1], [2, 1, 4, 3 ], [2] ] 이렇게 저장한다.
그런뒤 각 배열의 길이를 기준으로 오름차순으로 정렬한다. 그러면 [ [2], [2, 1], [1, 2, 3], [2, 1, 4, 3 ] ] 이렇게 된다.
그런다음 차례대로 배열을 조회하면서 처음인 정수들을 vector에 저장하면 [2, 1, 3, 4]의 순서로 저장된다.
처음에 문자열을 strtok로 분리하려다가 string과 char* 형변환 문제가 일어나서 그냥 만복문과 조건문으로 일일히 분리했다. 그리고 문제에서 튜플 규칙이 처음에 이해가 잘 안가서 규칙을 아는데 좀 시간이 걸렸다.
코드
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool check[100001];
bool comp(vector<int> &a, vector<int> &b) {
return a.size() < b.size();
}
vector<int> solution(string s) {
vector<int> answer;
int len = s.length();
vector<char> str;
vector<vector<int>> nums(500);
string num = "";
int idx = 0;
for (int i = 0; i < len; i++) {
if (s[i] == '{') {
str.push_back(s[i]);
}
else if (s[i] == '}') {
str.pop_back();
if (str.size() == 1) {
if (num != "") {
nums[idx].push_back(atoi(num.c_str()));
num = "";
}
idx++;
}
}
else if (s[i] == ',') {
if (str.size() == 2) {
if (num != "") {
nums[idx].push_back(atoi(num.c_str()));
num = "";
}
}
}
else { // num
num += s[i];
}
}
sort(nums.begin(), nums.begin() + idx, comp);
for (int i = 0; i < idx; i++) {
for (int n : nums[i]) {
if (!check[n]) {
check[n] = true;
answer.push_back(n);
break;
}
}
}
return answer;
}3번문제
[전체 사용자 아이디 목록]과 불량 사용자 목록에 매핑된 아이디인 [제제 아이디 목록]이 주어졌을 때 당첨에서 제외되어야 할 제재 아이디 목록은 몇가지 경우의 수가 가능한 지 return하는 문제.
예를 들어 [전체 사용자 아이디 목록]이 ["frodo", "fradi", "crodo", "abc123", "frodoc"]일 때,
[제제 아이디 목록]이 ["fr*d*", "abc1**"] 라면,
frodo abc123과 fradi abc123 두가지 경우가 가능하다.
풀이
각 제제 아이디 별로 전체 사용자 아이디에서 해당되는 아이디와 인덱스를 vector<pair<string, int>>에 저장한다.
그 다음 브루트포스로 모든 경우의 수를 찾아서 vector<vector <int>>에 저장한다. (제제 아이디 인덱스 목록)
중복된 경우의 수를 제외하고 size return.
이 문제는 모든 경우의 수를 찾다가 제제 아이디 패턴별로 각자 사용자 아이디가 겹쳐서 [1, 2, 4], [2, 1, 4] 이런식으로 경우의 수가 세지는 바람에 중복을 처리하는 방법을 생각하는 데 시간이 좀 걸렸다. "제재 아이디 목록들을 구했을 때 아이디들이 나열된 순서와 관계없이 아이디 목록의 내용이 동일하다면 같은 것으로 처리한다."라고 문제에 나와있었기 때문에 셀때 조건을 적용하는 것보다는 일단 다 세고나서 중복을 지우는 게 낫겠다. 싶어서 이렇게 풀었다. 마지막에 코드가 좀 난잡해 보인다;;; 다른 사람들은 어떻게 풀었으려나?
코드
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<pair<string, int>> cases[8];
vector<vector<int>> ans;
bool check[8];
void go(int index, int size, vector<int> &a)
{
if (index == size) {
ans.push_back(a);
return;
}
for (auto p : cases[index]) {
if (check[p.second]) continue;
check[p.second] = true;
a.push_back(p.second);
go(index + 1, size, a);
check[p.second] = false;
a.pop_back();
}
}
int solution(vector<string> user_id, vector<string> banned_id) {
int answer = 0;
int userSize = user_id.size();
int banSize = banned_id.size();
for (int i = 0; i < banSize; i++) {
int len = banned_id[i].length();
for (int j = 0; j < userSize; j++) {
if (len != user_id[j].length()) continue;
bool match = true;
for (int k = 0; k < len; k++) {
if (banned_id[i][k] == '*') continue;
if (banned_id[i][k] != user_id[j][k]) {
match = false;
break;
}
}
if (match) {
cases[i].push_back(make_pair(user_id[j], j));
}
}
}
vector<int> tmp;
go(0, banSize, tmp);
for (int i = 0; i < ans.size(); i++) {
sort(ans[i].begin(), ans[i].end());
}
sort(ans.begin(), ans.end());
ans.erase(unique(ans.begin(), ans.end()), ans.end());
answer = ans.size();
return answer;
}4번문제
호텔에 방이 총 K개가 있고 방법호는 1번부터 k번까지 있다. 다음 규칙에 따라 방을 배정할 때,
- 한 번에 한 명씩 신청한 순서대로 방을 배정한다.
- 고객은 투숙하기 원하는 방 번호를 제출한다.
- 고객이 원하는 방이 비어 있다면 즉시 배정한다.
- 고객이 원하는 방이 이미 배정되어 있으면 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정한다.
각 고객에게 배정되는 방 번호를 순서대로 배열에 담아 return하는 문제.
풀이
방법1 - 해시
숫자를 입력받았을 때 key 값을 반환하는 해시함수, 해시 배열을 탐색해서 값의 유무를 반환하는 함수를 만들었다. 그리고 고객이 원하는 방번호를 받아 없으면 저장, 있으면 방번호+1부터 K번 방까지 탐색해서 없으면 저장
방법2 - map 사용
해시함수를 직접 만드는 대신 key 값을 반환하는 함수만 두고, 이 함수에서 받은 key값과 방번호를 map에 저장하는 방식으로 구현. 뒤는 똑같음.
방법3 - set 사용
map을 set으로 변경
그밖에도 자잘자잘하게 코드를 계속 수정해보았지만 정확성 테스트는 다 통과해도 효율성 테스트를 통과하지 못함.ㅠㅠ
코드
- 이 문제는 계속 방법을 바꿔가며 푸느라 제출한 코드 개수가 너무 많고, 정확성 테스트는 항상 다 통과했지만 효율성 테스트는 계속 통과하지 못해서 게시하지 않음.
5번문제
징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어든다. 디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때는 그 다음 디딤돌로 한번에 여러 칸을 건너 뛸 수 있다. 디딤돌에 적힌 숫자가 순서대로 담긴 배열과 한 번에 건너뛸 수 있는 디딤돌의 최대 칸수가 주어졌을 때, 최대 몇 명까지 징검다리를 건널 수 있는지 return하는 문제
풀이
건널수 있는 최소인원을 1, 최대 인원을 배열의 최댓값으로 두고 이분탐색으로 건널 수 있는 최대 인원 찾는다. 인원수가 주어졌을 때 징검다를 건널수 있는지 여부를 반환하는 함수를 만들고, 최소, 최대값의 중간값을 넣어서 건널수 없으면 최대값을 줄이고, 건널수 있느면 최소값을 늘린다.
코드
#include <string>
#include <vector>
using namespace std;
vector<int> stepStones;
int size, K;
bool canCross(int n)
{
bool zero = false;
int cnt = 0;
for (int i = 0; i < size; i++) {
if (stepStones[i] < n) {
if (!zero) {
zero = true;
cnt = 1;
}
else {
cnt++;
}
if (cnt >= K) {
return false;
}
}
else {
zero = false;
cnt = 0;
}
}
return true;
}
int solution(vector<int> stones, int k) {
int answer = 0;
size = stones.size();
stepStones = stones; K = k;
int left = 1, right = 1;
for (int i = 0; i < size; i++) {
if (right < stones[i]) {
right = stones[i];
}
}
while (left <= right) {
int mid = (left + right) / 2;
if (canCross(mid)) {
if (answer < mid) {
answer = mid;
}
left = mid + 1;
}
else {
right = mid - 1;
}
}
return answer;
}문제 난이도는 적당했다. 어느정도 고민한 문제도 있지만 풀지 못한 문제는 없었다. 확실히 공채보다는 인턴 코딩테스트가 더 난이도가 쉬운거 같다. 4번 문제의 효율성 테스트를 통과 못한게 아쉽지만;;;
다행히 작년보단 실력은 조금 늘은것 같긴 하다. 작년 하반기에는 코딩테스트 볼 때 중간 난이도 이상부터는 잘 못풀거나, 다 풀어도 정확도가 떨어지는 경우가 대부분이었는데. 열심히 알고리즘 공부한 보람은 있나보다. 올해 하반기 쯤 되면 좀 더 나아져 있으려나?