2020 카카오 블라인드 신입 공채 1차 코딩 테스트 후기 및 문제 풀이

카카오 블라인드 신입 공채 코딩 테스트

방학 기간을 백준에 갈아넣은 뒤 처음 본 코딩 테스트이다.

물론 공채를 위한 대회이지만 2020년 졸업 예정자가 아니어도 참여 가능하다고 하기에 바로 지원해서 도전해보게 되었다.

2020 블라인드 코딩 테스트 후기

2019 문제들을 어제 풀어봤는데 대부분이 구현에 초점이 맞춰져있고 뒤에 난이도가 있는 문제들은 알고리즘을 이용해서 푸는 문제들이었다.(구현은 실수 없이 문제를 정확히 해석하는 것이 제일 중요한 듯하다.)

올해도 마찬가지로 앞 문제들은 구현에 초점을 맞추고 있었다.

4번 문제가 효율성을 따지는 문제로 시간 효율을 위해 특정 알고리즘이 필요한 듯했고 5번까지 문제를 접한 나에게는 4번을 제외한 문제들은 구현의 문제로 다가왔었다.

다행히 4번을 빠르게 손절함으로써 알고리즘 공부 4개월 차인 나는 4시간 반만에 4문제를 풀었다.

내가 푼 문제인 1, 2, 3, 5번 문제에 대한 내 나름의 풀이를 적어보려 한다.

문제 해설

프로그래밍1

이 문제는 s를 쪼개는 단위인 k를 1개부터 n/2개까지 보면서 k일 때의 압축된 글자의 수 cnt를 확인한다. 이를 위해 i번째(비교대상)와 j번째(그 뒤에 샘플)를 비교해나간다.

두개가 같다면 j를 i + k로 업데이트 해서 다시 비교해주고 same_n의 개수를 늘린다.

다르다면 그떄는 same_n의 개수를 확인해서 이에 맞게 cnt를 업데이트해준다.

그리고 모든 k의 cnt 중에서 제일 작은 값을 ans로 반환한다.

주의할점!

압축한 횟수를 나타낼때 10 이상이면 2자리 100이상이면 3자리 1000이상이면 4자리가 된다. 이에 맞춰서 추가하지 않았을 때 한 60퍼센트정도 맞은 거 같다..^^

#include <string>
#include <vector>
using namespace std;

int solution(string s) {
    int n = s.length(), ans = n;
    for(int k = 1; k <= n/2; k++){
        int cnt = 0, i = 0;
        //비교대상 i
        while(i < n){
            int same_n = 0, next = 0;
            if(i + k > n){
                cnt+= n - i; break;
            }
            //샘플 j
            for(int j = i+k; j < n; j+=k){
                //비교시작
                int t;
                for(t = 0; t < k; t++){
                    //다른게 하나라도 있으면 0으로
                    if(s[i+t] != s[j+t])break;
                }
                if(t == k) same_n ++;
                else {
                    next = j; break;
                }
            }
            if(same_n){
                if(same_n + 1 <= 9)cnt += k + 1;
                else if(same_n + 1 <= 99)cnt += k + 2;
                else if(same_n + 1 <= 999)cnt += k + 3;
                else  cnt += k + 4;
            }
            else cnt+= k;
            if(next == 0)break;
            i = next;
        }
        if(cnt < ans) ans = cnt;
    }
    return ans;
}

프로그래밍 2

이 문제는 알고리즘을 다 주기 때문에 이에 따라 얼마나 잘 구현해내는 가에 대한 문제이다.

괄호 set의 범위가 주어지면 거기서 u와 v 경계 지점(i)을 구해주고 u의 맞고 안맞고를 확인해주기(result) 위해 correct 함수를 만들었다.

만약 correct 함수에서 begin과 end가 같을 때는 그냥 begin과 1을 반환해주었다.

v의 범위가 s 범위 밖으로 벗어나는 것을 방지하기 위해 다음을 해줘야 한다.

if(x2 >= n || y2 >= n)s2 = "";

그냥 psudo code를 따라가고 디버깅하다보면 풀 수 있는 문제이다.

#include <string>
#include <vector>
#include <stack>
#define pii pair<int, int>
using namespace std;

string p;
int n;
pii correct(int begin, int end){
    stack<int> s; 
    int result = 1;
    int o = 0, x = 0;
    for(int i = begin; i <= end; i++){
        if(p[i] == ')') {
            o++;
            if(s.empty()) result = 0;
            else s.pop();
        }
        else {
            s.push(1); x++;
        }
        if(o == x) return pii(i, result);
    }
    return pii(begin, 1);
}

string _solution(int begin, int end){
    string result = "";
    if(begin == end) return "";
    pii r = correct(begin, end);
    int x1 = begin, y1 = r.first, x2 = r.first + 1, y2 = end;
    string s2 = "";
    if(x2 >= n || y2 >= n)s2 = "";
    else s2 = _solution(x2, y2);
    if(r.second)return p.substr(x1, y1 - x1 + 1) + s2;
    result = "(" + s2 + ")";
    for(int i = x1 + 1; i <= y1 - 1; i++){
        if(p[i] == '(') result += ")";
        else result += "(";
    }
    return result;
}

string solution(string _p) {
    p = _p, n = p.length();
    return _solution(0, n-1);
}

프로그래밍 3

이 문제는 일단 key를 사방향으로 돌린 결과를 keys에 저장하고 5중 for문을 돌리면 된다..ㅎㅎ

key의 위치만 중요한 것이 아니라 각각의 맞물리는 지점이 둘다 튀어나온 것은 아닌지 확인해줘야 하기에 전체를 다 확인해주었다.

주의할점!

key가 좌측 위로 가고 lock이 우측 하단에 있을 때 열릴 수도 있기 때문에 비교를 -m, -m부터 시작해야 한다.

#include <string>
#include <vector>
using namespace std;
bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    int keys[4][21][21], m = key.size(), n = lock.size(), locks = 0;
    for(int i = 0; i < m; i++){
        for(int j = 0; j < m; j++){
            keys[0][i][j] = key[i][j];
            keys[1][i][j] = key[m - j - 1][i];
            keys[2][i][j] = key[m - i - 1][m - j - 1];
            keys[3][i][j] = key[j][m - i - 1];
        }
    }
    for(int x = 0; x < n; x++){
        for(int y = 0; y < n; y++){
            if(lock[x][y] == 0) locks++;
        }
    }
    if(locks == 0)return true;
    for(int x = - m; x < n; x++){
        for(int y = - m; y < n; y++){
            for(int k = 0; k < 4; k++){
                int cnt = 0, wrong = 0;
                for(int i = 0; i < m; i++){
                    for(int j = 0; j < m; j++){
                        if(x + i < 0 || y + j < 0 || x + i >= n || y + j >= n) continue;
                        if(keys[k][i][j] == 1 && lock[x + i][y + j] == 0)cnt ++;
                        else if(keys[k][i][j] == 1 && lock[x + i][y + j] == 1){
                            wrong = 1;
                            break;
                        }
                    }
                    if(wrong)break;
                }
                if(cnt == locks && !wrong) return true;
            }
        }
    }
    return false;
}

프로그래밍 5

이 문제도 구현을 잘할 수 있는 가에 조금의 트릭이 추가된 문제이다.

해당 명령이 주어졌을 때 명령에 해당하는 값을 수행하기에 합당한지 확인하기 위해 3개의 함수를 만들었다.(기둥 추가, 보 추가, 제거)

기둥 추가, 보 추가의 조건을 잘 적용시키는 것이 뽀인트다.

그리고 삭제 시에는 해당 기둥 혹은 보를 제거한 후 모든 원소를 각각 뺐다가 다시 추가할 때 모두 조건을 성립하는지 확인했다. 성립시 삭제, 하나라도 문제 생기면 삭제 x.

주의할점!

같은 지점에 보와 기둥이 둘다 들어갈 수 있기 때문에 arr를 3차원으로 준비한다.

#include <string>
#include <vector>

using namespace std;

int arr[102][102][2], n;
//기둥 0
int insert_gidung(int x, int y){
    if(arr[x][y][1]){
        arr[x][y][0] = 1;
        return 1;
    } 
    if(x - 1 >= 0 && arr[x - 1][y][1]){
        arr[x][y][0] = 1;
        return 1;
    }
    if(y == 0){
        arr[x][y][0] = 1;
        return 1;
    }
    if(y - 1 >= 0 && arr[x][y-1][0]){
        arr[x][y][0] = 1;
        return 1;
    }
    return 0;
}
//보 1
int insert_bo(int x, int y){
    if(y - 1 >= 0 && (arr[x][y - 1][0] || arr[x + 1][y - 1][0])){
        arr[x][y][1] = 1;
        return 1;
    } 
    if(arr[x + 1][y][1] && x - 1 >= 0 && arr[x - 1][y][1]){
        arr[x][y][1] = 1;
        return 1;
    }
    return 0;
}

int erase(int x, int y, int what){
    int result = 1;
    arr[x][y][what] = 0;
    for(int i = 0; i < n + 1; i++){
        for(int j = 0; j < n + 1; j++){
            for(int k = 0; k < 2; k++){
                if(arr[i][j][k] == 1){
                    arr[i][j][k] = 0;
                    if(k == 0){
                        if(!insert_gidung(i, j))result = 0;
                    }
                    else {
                        if(!insert_bo(i, j))result = 0;
                    }
                    arr[i][j][k] = 1;
                }
            }
        }
    }
    if(!result) arr[x][y][what] = 1;
    return result;
}


//기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다.
//보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.
//[[1,0,0,1],[1,1,1,1],[2,1,0,1],[2,2,1,1],[5,0,0,1],[5,1,0,1],[4,2,1,1],[3,2,1,1]]	
vector<vector<int>> solution(int _n, vector<vector<int>> build_frame) {
    n = _n;
    vector<vector<int>> answer;
    for(int i = 0; i < build_frame.size(); i++){
        int what = build_frame[i][2];
        int how = build_frame[i][3];
        int x = build_frame[i][0];
        int y = build_frame[i][1];
        //기둥 지을때
        if(how == 1 && what == 0)insert_gidung(x, y);
        else if(how == 1 && what == 1)insert_bo(x, y);
        else erase(x, y, what);
    }
    for(int i = 0; i < n + 1; i++){
        for(int j = 0; j < n + 1; j++){
            for(int k = 0; k < 2; k++){
                if(arr[i][j][k] == 1){
                    vector<int> arr(3);
                    arr[0] = i, arr[1] = j, arr[2] = k;
                    answer.push_back(arr);
                }
            }
        }
    }
    return answer;
}

알고리즘 대회 참가의 필요성

이번 대회를 나가면서 시간의 제약 없이 백준을 푸는 것과 대회에서 문제를 푸는 것은 큰 차이가 있음을 느꼈다.

각종 코딩 대회에 대한 정보를 정리해봤는데 대회 관련 정보가 궁금하다면 다음 사이트를 참고하기 바란다.

각종 코딩대회 정보 정리