2020카카오 블라인드 신입 개발자 공채 코딩테스트 후기

눈물의 2솔

5시간동안 7문제를 풀어야하는 카카오 블라인드 신입 개발자 공채 코딩테스트 후기입니다.

금년 알고리즘을 처음 시작해서 어느덧 1년차까지 3개월.. 나름 열심히 공부했다고 생각했는데 이번 코딩테스트 결과를 보니 정말 참담했습니다. 합격컷이 3~4솔정도 된다고해서 5시간 내에 최소 3솔은 할 수 있을 줄 알았는데... 저의 실력에 감탄하고 갑니다.

내가 푼 문제

1번. 비손실 압축하기

aaabbbaccc => 3a3ba3c 이런식으로 바꾸어주는 문제였습니다.
저같은 경우 for문 내에서 vector 배열 생성해주고, 1칸씩 담기, 2칸씩 담기, 3칸식 담기... length()/2칸씩 담기까지 돌려주었습니다. 길이의 반 이상으로 담는 것은 의미가 없기 때문에..? 반까지만 담아주었습니다.
그런다음 해당 문자열이 다음 문자열과 같으면 번호를 하나씩 올려주고, 다르면 count와 함께 스트링에 추가해주는 방식으로 진행하였습니다. 그렇게 해서 배열 끝까지 다 탐색한다면, 결과물이 3a3ba3c 처럼 나오겠지요? (아 1개 있는 경우에는 쓰지 않는다는 예외 처리도 해주었습니다.) 그럼 그 길이를 answer와 비교해서 작은 값을 넣어주는 방식을 선택하였습니다. answer의 초기값은 MAX값입니다.
코드로 구현하는데 애를 상당히 많이 먹었습니다. 문자열 처리를 평소 공부하지 않았던 저의 탓이겠지요..

배웠던 점

substr 이라는 좋은 함수 배우고 갑니다.

코드

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

int solution(string s) {
    if (s.length() == 1)return 1;
    int answer = 987654321;
    for (int t = 1; t <= s.length() / 2; t++) {
        vector<string> arr;
        for (int i = 0; i < s.length(); i += t) {
            string s2 = s.substr(i, t);
            arr.push_back(s2);
        }
        arr.push_back("A");// 마지막 문자열 처리하기
        // 문자열 자른거 가져 와서
        int len = arr.size();
        int c = 0;
        string tmp;
        for (int i = 0; i < len-1; i++) {
            c++;
            if (arr[i] != arr[i + 1]) {
                if (c == 1)tmp += arr[i];
                else {
                    tmp += to_string(c);
                    tmp += arr[i];
                }
                c = 0;
            }
        }
        //cout << tmp << endl;
        if (answer > tmp.length())answer = tmp.length();
    }
    return answer;
}

int main()
{
    string s;
    cin >> s;
    cout << solution(s);
}

2번. 올바른 괄호 배열 맞추기?

제목이 이런 느낌이었던 것 같은데.. 시뮬레이션 문제였습니다. 문제에서 시키는 대로 구현했더니 그냥 통과되었습니다.

배웠던점

문제 풀기전에 손으로 한번 시뮬레이션 돌려보는거.. 그리고나서 그대로 코드화 시키는 작업이 상당히 중요하다는 것을 알았습니다.

코드

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

string solution(string p) {
    if (p == "")return "";
    string answer = "";
    vector<char> arr;
    for (int i = 0; i < p.length(); i++) {
        arr.push_back(p[i]);
    }
    string u, v;
    string tmp = "";
    int c1=0;    // ( count 
    int c2=0;    // ) count
    for (auto i = arr.begin(); i != arr.end(); i++) {
        if (*i == '(')c1++;
        else c2++;
        if (c1 == c2) {
            u.assign(arr.begin(),i+1);
            v.assign(i + 1, arr.end());
            break;
        }
    }
    // u가 올바른 문자열인지 확인해보자
    stack<char> st;
    for (int i = 0; i < u.length(); i++) {
        if (u[i] == '(')st.push(u[i]);
        else if (u[i] == ')') {
            if (st.size() == 0) {
                st.push('N');
                break;
            }
            st.pop();
        }
    }
    // 올바른 문자열
    if (st.size() == 0) {
        u += solution(v);
    }
    else {
        //4 - 1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
        string ttmp = "(";
        //4 - 2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
        ttmp += solution(v);            // v=()(
        //4 - 3. ')'를 다시 붙입니다.
        ttmp += ")";
        //4 - 4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
        //u = u.substr(1);
        u = u.substr(1, u.length() - 2);
        string asdf = "";
        for (int i = 0; i < u.length(); i++) {
            if (u[i] == '(') asdf += ")";
            else asdf += "(";
        }

        //4 - 5. 생성된 문자열을 반환합니다.
        ttmp += asdf;
        return ttmp;
    }

    answer = u;

    return answer;
}

int main() {
    string p = "(()())()";
    cout << solution(p);

    return 0;
}

여기까지가 제가 완벽하게 통과했던 문제들입니다. 테케 통과되는거 보면서 소리질렀네요 너무 좋아서.. 하지만 이 두문제 다 풀때 쯤 이미 3시간 반이 지나있었습니다.

3번. 문제 읽었으나 이해못해서 넘어감

4번. 문제 읽었으나 이해못해서 넘어감

5번. 문제 읽었으나 이해못해서 넘어감

6번. 문제 읽었으나 이해못해서 넘어감

여기서부터 1차 맨붕.. 뭐G.. 카카오 뭐야.. 무서워..

7번. 드론 이동시키기

사실 이건 삼성 3월 a형에 나왔던 문제와 거의 유사하게 풀 수 있었습니다. 그래서 7번을 보는 순간 아 3솔까지는 거저 하겠구나~ 싶었습니다.어림도 없지! 테스트케이스 정답은 당연히 맞았는데 제출하니 모두 틀렸다그래서 그때부터 맨붕이 왔습니다.
제가 생각한 로직은 앞축 뒤축 기준을 주고 시계방향, 반시계방향 회전시까지 모두 고려해서 작성해주는 것인데 역시나 테케는 맞았는데 정답은 아니어서 하.. 3솔은 힘들겠구나하는 슬픈 예감이 들었습니다... 끝까지 포기하지 않고 계속 작성했지만 결과는 fail.. 코드 공유합니당.(혹시 원인이 뭔지 아시는 분은 댓글좀 남겨주시면 감사하겠습니당)

#include <string>
#include <vector>
#include<iostream>
using namespace std;
vector<vector<bool>> visited;
vector<vector<int>> memo;
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
int res;
void dfs(vector<vector<int>> board, int y, int x, int dir, int N, int time) {
    if (y == N - 1 && x == N - 1) {
        if (res > time)res = time;
    }

    if (memo[y][x] > time) {
        memo[y][x] = time;
    }
    else {
        return;
    }
    // 오른쪽 이동
    if (dir == 0) {
        if (0 <= y && y < N && 0 <= x + 1 && x + 1 < N) {
            // 가고자 하는 곳이 안전한 영역이고, 방문하지 않았을 경우 : 왼쪽!
            if (board[y][x + 1] == 0 && !visited[y][x + 1]) {
                visited[y][x + 1] = true;
                dfs(board, y, x + 1, 0, N, time + 1);
                visited[y][x + 1] = false;
            }
        }
        // 앞축 아래로 회전
        if (0 <= y + 1 && y + 1 < N && 0 <= x && x < N) {
            if (board[y + 1][x] == 0 && board[y + 1][x - 1] == 0 && !visited[y + 1][x]) {
                visited[y + 1][x] = true;
                dfs(board, y + 1, x, 1, N, time + 1);
                visited[y + 1][x] = false;
            }
        }
        // 뒤축 아래로 회전
        if (0 <= y + 1 && y + 1 < N && 0 <= x-1 && x-1 < N) {
            if (board[y+1][x - 1] == 0 && board[y+1][x]==0 && !visited[y + 1][x]) {
                visited[y + 1][x-1] = true;
                dfs(board, y + 1, x-1, 1, N, time + 1);
                visited[y + 1][x-1] = false;
            }
        }
        // 앞축 위로 회전
        if (0 <= y - 1 && y - 1 < N && 0 <= x && x < N) {
            if (board[y - 1][x - 1] == 0 && board[y - 1][x] == 0 && !visited[y - 1][x]) {
                visited[y - 1][x] = true;
                dfs(board, y - 1, x, 1, N, time + 1);
                visited[y - 1][x] = true;
            }
        }
        // 뒤축 위로 회전
        if (0 <= y - 1 && y - 1 < N && 0 <= x-1 && x-1 < N) {
            if (board[y-1][x] == 0 && board[y-1][x-1]==0 && !visited[y - 1][x-1]) {
                visited[y - 1][x-1] = true;
                dfs(board, y - 1, x-1, 1, N, time + 1);
                visited[y - 1][x-1] = true;
            }
        }
    }
    // 세로 이동
    else if (dir == 1) {
        if (0 <= y + 1 && y + 1 < N && 0 <= x && x < N) {
            // 가고자 하는 곳이 안전한 영역이고, 방문하지 않았을 경우 : 아래!
            if (board[y + 1][x] == 0 && !visited[y + 1][x]) {
                visited[y + 1][x] = true;
                dfs(board, y + 1, x, 1, N, time + 1);
                visited[y + 1][x] = false;
            }
        }
        // 앞축 오른쪽  회전
        if (0 <= y && y < N && 0 <= x + 1 && x + 1 < N) {
            // 범위 내부에 존재하고, 가고자 하는 칸을 방문하지 않았을 경우에 방향 전환.
            if (board[y][x + 1] == 0 && board[y - 1][x + 1] == 0 && !visited[y][x + 1]) {
                visited[y][x + 1] = true;
                dfs(board, y, x + 1, 0, N, time + 1);
                visited[y][x + 1] = false;
            }
        }
        // 뒤축 오른쪽 회전
        if (0 <= y - 1 && y - 1 < N && 0 <= x + 1 && x + 1 < N) {
            if (board[y][x + 1] == 0 && board[y - 1][x + 1] == 0 && !visited[y - 1][x + 1]) {
                visited[y - 1][x + 1] = true;
                dfs(board, y - 1, x + 1, 0, N, time + 1);
                visited[y - 1][x + 1] = false;
            }
        }
        //앞축 왼쪽 회전
        if (0 <= y && y < N && 0 <= x - 1 && x - 1 < N) {
            if (board[y - 1][x - 1] == 0 && board[y][x - 1] == 0 && !visited[y][x - 1]) {
                visited[y][x - 1] = true;
                dfs(board, y, x - 1, 0, N, time + 1);
                visited[y][x - 1] = true;
            }
        }
        // 뒤축 왼쪽 회전
        if (0 <= y - 1 && y - 1 < N && 0 <= x - 1 && x - 1 < N) {
            if (board[y - 1][x - 1] == 0 && board[y][x - 1] == 0 && !visited[y - 1][x - 1]) {
                visited[y - 1][x - 1] = true;
                dfs(board, y - 1, x - 1, 0, N, time + 1);
                visited[y - 1][x - 1] = true;
            }
        }
    }
    return ;
}

int solution(vector<vector<int>> board) {
    int N = board.size();
    board[0][0] = 9;
    board[0][1] = 9;
    visited.assign(N, vector<bool>(N, 0));
    memo.assign(N, vector<int>(N, 987654321));
    visited[0][0] = true;
    visited[0][1] = true;
    res = 987654321;
    dfs(board, 0, 1, 0, N, 0);

    int answer = res;
    if (answer == 987654321) {
        return 
    }
    return answer;
}
int main() {

    vector<vector<int>> board = { {0, 0, 0, 1, 1 }, { 0, 0, 1, 1, 0 }, { 0, 1, 0, 1, 1 },
    { 1, 1, 0, 0, 1 }, { 0, 0, 0, 0, 0 } };
    cout << solution(board);

    return 0;
}

결론

2시부터 7시까지 치뤄진 기나긴 코딩테스트였습니다! 세상엔 역시 고수님들이 많다는 것을 느꼈습니다.2시간 반만에 올클하시고 후기를 작성하고 계신분도 계셨고, 기본 3~4솔은 다들 푸신 것 같더라구요ㅎㅎㅎ 하지만 뭐 어떻습니까! 아직 발전할 기회가 남아있다는 것으로 만족하고 더욱 더 공부에 매진하도록 노력해봐야겠지요.

이상 2020 카카오 코딩테스트 후기였습니다~