프로그래머스 문자열 압축(2020 KAKAO BLIND RECRUITMENT)

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

코딩테스트 연습 - 문자열 압축

문제 접근법 : 

문자열을 압축하기위해서 최대로 압축한다면 반으로 쪼개는것이 가장 효과적입니다.

하지만 그렇지않은경우가 더많을테니

length의 길이가 1부터 s의 길이의 반까지 전부 압축이 가능한지 확인하여 가장 짧은 길이를 반환해주면 되는문제니

문자열만 잘다루면 되는 문제입니다.

 

소스코드 : 

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

//By 콩순이냉장고 #include <bits/stdc++.h> using namespace std; int solution(string s) {     int answer = s.size();     for (int len = 1; len <= s.size() / 2; len++) {         string res;         for (int i = 0; i< s.size();) {             string t = s.substr(i, len);             int cnt = 1;             for (int j = i + len; j <= s.size(); j += len) {                 if (t == s.substr(j, len))                     cnt++;                 else                     break;             }             if (cnt == 1)                  res += t;                else                 res += to_string(cnt) + t;             i += len * cnt;         }        // cout << len << " " << res << " " << res.size() << endl;         answer = min(answer, (int)res.size());     }     return answer; } Colored by Color Scripter

cs

 

궁금한점 혹은 모르는점 또는 논리적인 오류등 어떤 질문이든 댓글은 언제나 환영입니다 ㅎㅎ