[2020 KAKAO BLIND RECRUITMENT] 문자열 압축

알고리즘/프로그래머스

[2020 KAKAO BLIND RECRUITMENT] 문자열 압축

동 코 2020. 3. 16. 18:15

풀이과정

검사는 단위별로 진행한다.

일치하는 경우에는 그대로 다음 단위를 검사

일치하지 않는 경우에는 출력할 string에 출력한다.

이때, 1인경우에는 숫자를 출력하지 않으므로 따로 처리해준다.

주의사항 문자열의 길이가 1인경우가 존재한다 이를 잘 처리해줘야됨. 테스트 케이스 5번이 아마 문자열 길이가 1일것일거같다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#include <string>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;
 
int unit_mapping(string str, int unit) {
    string result = "";
    int same_cnt = 1;
    for (int i = 0; i < str.length(); ) {
        int cnt = 0;
 
        for (int j = 0; j < unit; j++) {
            if (i + (same_cnt*unit) + j > str.length()) break;
            if (str[i + j] == str[i + (same_cnt*unit) + j])
                cnt++;
            else break;//일치하지 않는다면
        }
        if (cnt == unit) { //일치하는 경우
            same_cnt++;
        }
        else {
            if (same_cnt == 1) {
                result += str.substr(i, unit);
                i += unit;
            }
            else {
                string int_str = to_string(same_cnt);
                result += int_str;
                result += str.substr(i, unit);
                i = i + same_cnt * unit;
                same_cnt = 1;
            }
 
        }
    }
    //cout << result << endl;
    return result.size();
}
 
 
int solution(string s) {
    int min_size = INT_MAX;
    int size = 0;
    if (s.length() == 0)
        min_size = 0;
    for (int i = 1; i <= s.length() / 2 + 1; i++) {
        size = unit_mapping(s, i);
        min_size = min(min_size, size);
    }
    return min_size;
}
h

 

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/60057