2020 카카오 신입 개발자 블라인드 채용 1차 코딩 테스트 1번


작성일 : 2019-12-10 01:28:17
조회수 : 200



본문

2019년엔 단 하나의 글도 포스팅하지 못한 저에게 우선 반성합니다.. ㅠㅠ

일이 바쁘단 핑계로 슬금슬금 놓아버리다 어느새 방치도 되고, 서버가 중간에 문제가 생겨 복원도 힘들게 하면서 우여곡절 끝에 다시 포스팅을 시작합니다.


2020 신입 개발자 1차 테스트는 우선 정답률이 2018, 2019에 비해 전체적으로 굉장히 낮은 것을 알수 있었습니다.




2020 1차

2019 1차

1번

25.9%

59.91%

2번

23.1%

55.57%

3번

7.4%

16.09%

4번

34.4%/0.8%

42.08%/5.52%

5번

1.9%

7.40%

6번

0.6%

6.12%

7번

1.4%

5.85%


기업별로 목표하는 코딩테스트의 난이도가 각각 다르겠지만, 이번 카카오 문제는 꽤나 어려운 난이도였다는 것을 알 수 있었습니다. 과연 저도 다 풀 수 있을지.. 걱정이 됩니다.






이제 1번 포스팅을 시작하겠습니다.


1번 문제는 주어진 문자열을 앞에서부터 일정한 길이로 잘랐을 때, 가장 압축이 잘 될 수 있는 길이를 찾아 자르고, 이 때 압축된 문자열의 최소 길이를 출력하는 문제입니다. 공채에서는 기본적으로 STL을 모두 사용할 수 있으므로, 또 문자열의 최대 길이가 1000 이므로 어느정도 최적화를 하지 않고도 풀 수 있음을 알 수 있습니다. 


문자열이 압축되기 위해서는 같은 문자열이 반복되야하므로, 잘라볼 수 있는 최대의 길이는 문자열 전체 길이의 절반임이 자명합니다. 단 1글자일 경우 length / 2가 0으로 저장될 수 있으므로 전처리를 해주면 됩니다. 또 초반에 은근 삽질한 케이스가 하나 있는데, 압축을 했을 때 같은 문자열이 반복되면 그 횟수를 저장하는 숫자 역시 길이를 체크해 주어야 한다는 점입니다. 즉, len(aaa....aa) = 1000 일 때, 이를 압축하면 1000a 가 되므로 문자열의 길이는 5라는 점입니다. 또한 1일 때는 숫자가 생략될 수 있다는 점도 포인트입니다.


요런 포인트만 놓치지 않고 잡는다면 나머진 직접 구현하면 되므로 별로 어렵지 않은 문제입니다.

int solution(string s) {
    if (s.length() == 1) return 1;
    int len = s.length(), ans = 1001;
    for (int i = 1; i <= len/2; i++) {
        int cmp = 0;
        for (int j = 0; j < len;) {
            if (j + i >= len) {
                cmp += len - j;
                break;
            }
            int pos = j, cnt = 1;
            string dest = s.substr(pos, i);
            while (1) {
                pos += i;
                if (dest.compare(s.substr(pos, i)) != 0) break;
                cnt++;
            }
            cmp += i;
            if (cnt > 1) cmp += to_string(cnt).length();
            j = pos;
        }
        if (ans > cmp) ans = cmp;
    }
    return ans;
}

2020 카카오 신입 개발자 블라인드 채용 1차 코딩 테스트 1번 - 알고리즘닷컴
취업 대비 알고리즘에서는 다양한 기업들의 기출 문제 및 경향, 풀이 등에 대한 포스팅을 다룹니다.