카카오 입사시험_문자열 압축: 문제 1-3

자 이제 마지막 문제이다. 이는 카카오톡의 입사시험 문제로 출제되었다!

 

위에서는 1개의 문자의 반복, 2개 연속 문자들의 반복을 이용하여 문자열을 압축하였다.

이제 이를 단위를 3개 이상까지 확장하여 문자열을 압축해보려 한다.

 

"abcabcdede"와 같은 경우, 문자를 2개의 단위로 자르면 ab/ca/bc/de/de 이므로 이를 압축하면 "abcabc2de”가 되지만 , 3개 단위로 자른다면 abc/abc/ded/e이므로  "2abcdede”가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다. (단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 된다)

 

압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return하도록 함수를 완성해주세요

 

예 #1

aabbaccc

7

예  #2

ababcdcdababcdcd

9

예  #3

abcabcdede

8

예  #4

abcabcabcabcdededededede

14

예  #5

xababcdcdababcdcd

17

 

위의 실행 예에 대한 설명

입출력 예 #1 문자열을 1개 단위로 잘라 압축했을때 가장 짧습니다.

입출력 예 #2 문자열을 8개 단위로 잘라 압축했을때 가장 짧습니다.

입출력 예 #3 문자열을 3개 단위로 잘라 압축했을때 가장 짧습니다.

입출력 예 #4 문자열을 2개 단위로 자르면 "abcabcabcabc6de” 가 됩니다. 문자열을 3개 단위로 자르면 "4abcdededededede” 가 됩니다. 문자열을 4개 단위로 자르면 "abcabcabcabc3dede”가 됩니다. 문자열을 6개 단위로 자를 경우 "2abcabc2dedede”가 되며, 이때의 길이가 14로 가장 짧습니다.

입출력 예 #5 문자열은 제일 앞에서부터 정해진 길이만큼 잘라야 합니다. 따라서 주어진 문자열을 x / ababcdcd / ababcdcd 로 자르는 것은 불가능 합니다. 이 경우 어떻게 문자열을 잘라도 압축되지 않으므로 가장 짧은 길이는 17이 됩니다.

 

출제의도

문자열을 다룰 수 있고, 아래 예시와 같이 문자열과 관련된 다양한 작업을 할 수 있는지 파악

 

문자열 자르기

부분 문자열 얻기

문자열 비교하기

문자열 길이 얻기

 

문제 풀이

첫 번째로 배치된, 가장 쉬운 문제입니다. 문자열 길이가 최대 1,000으로 제한이 크지 않기 때문에, 가능한 모든 방법을 탐색하면 됩니다. 문자열 길이가 N일 때, 길이가 N/2 보다 크게 잘랐을 때는 길이가 줄지 않습니다. 따라서 1 ~ N/2 길이로 자르는 방법을 모두 탐색한 후 그중 가장 짧은 방법을 선택하면 됩니다.

 

가장 쉬운 문제라고 했는데 카카오에서 공개한 정답률이 25.9%이다

그말은 4명중 1명만이 맞췄다는 건데...

쉬운게 쉬운게 아닌데?

그리고 아무리 단계별로 쉽게 풀어 내셨다지만 이 문제를 1학년 기말고사로 내시는 교수님은 대체...

 

일주일을 통으로 고민하다 풀었다

사실 이 문제는 내장함수를 많이 사용해야 쉽게 풀수 있다

내가 컴프 기말때 못풀었던 이유도 내장함수를 사용하지 않고 반복문으로 풀어서..

int solution(char* s, int cutLen) //ababccdddd라 하면 ab가 str1, ab가 str2
{
    int i, j = 0;
    int len;
    int q;
    int k;
    char temp[1000] = "";
    char str1[501] = "";
    char str2[501] = "";
    char flag[20]; //임시 버퍼
    int digit;
 
    strncpy(str1, s, cutLen);//strncpy로 초기값 설정
 
    len = 1;
    for (q = cutLen; q < strlen(s); ) { //달라지고
        for (k = 0; k < cutLen; k++, q++) {
            str2[k] = s[q];
        }
 
        if (strcmp(str1, str2) == 0) //str1과 str2가 같으면
            len++;
        else { //다르면
            if (len > 1) { //sprintf로 숫자를 문자열로 바꾸고 strcat로 
                sprintf(flag, "%d", len);
                strcat(temp, flag);
            }
 
            strcat(temp, str1, cutLen);//strcat으로 문자를 넣기
 
            strcpy(str1, str2); //strcpy
            len = 1; //길이 초기화
        }
    }
 
    if (len > 1) {
        sprintf(flag, "%d", len);
        strcat(temp, flag);
    }
 
    strncat(temp, str1, cutLen);//strcat으로 문자를 넣기
 
    printf("%s\n", temp);
 
    return strlen(temp);
}
int main(void)
{
    char s[1001];
    int shortLen = 1001; //압축이 안되도 그 길이는 1001보다 작음
    int rslt;
    scanf("%s", s);
 
    for (int i = 1; i <= strlen(s) / 2; i++) {
        rslt = solution(s, i);
        if (rslt < shortLen)
            shortLen = rslt;
    }
 
    printf("\n%d\n", shortLen); // 문제-3)
}

 

sprinf함수를 그리고 컴프 시간에 안배웠다

 

sprinf (buff,출력형식,변수)라 하면 buff에 변수가 출력형식대로 저장된다

예를 들어 나는 sprintf(flag, "%d", len) 라 적었으니 문자열인 len이 %d니까 정수형으로 flag배열에 저장된다