[2020 kakao blind recruitment] lv2 문자열 압축(cpp/python)

 

문자열 압축

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

문제 설명

주어지는 문자열을 특정 길이만큼 잘라서 같은 문자면 숫자로 바꿔 표시했을 때의 (1은 생략) 그 문자열의 길이가 가장 짧은 순간을 찾는 문제

 

처음에는 1부터 주어지는 문자열의 길이만큼 자를 길이를 늘려가며 모두 탐색해야하나 싶었지만, 잘 생각해보면 해당 길이만큼의 중복되는 문자열을 찾는 것이므로, 문자열의 길이/2만큼만 탐색하면된다.

 

문제 풀이

소스코드 : C++

예전 풀이

#include<iostream>
#include <string>
#include <vector>
#include <queue>
#include<algorithm>

using namespace std;

int solution(string s) {
    int answer = s.size();
    for (int len = 1; len < s.size(); len++) {    //스플릿 길이
        int res = 0;
        string test;
        queue<pair<string, int>> q;
        q.push({ s.substr(0, len),0 });
        while (!q.empty()) {
            string cur = q.front().first;
            int idx = q.front().second;
            q.pop();
            int cnt = 0;
            for (int i = idx; i < s.size(); i += cur.size()) {
                string tmp = s.substr(i, cur.size());
                if (cur != tmp) {
                    q.push({ tmp,i });
                    break;
                }
                else {
                    cnt++;
                }
            }
            if (cnt > 1) res += to_string(cnt).size();
            test += cur;

            res += cur.size();
        }
        answer = min(res, answer);
    }
    return answer;
}

 

 

큐에 비교할 문자와 시작 인덱스를 넣어주고, 탐색을 시작한다. 현재 비교대상인 문자열(cur)과 for문에서 비교할 문자열을 잘라가며 비교해준다.

 

만약 현재 비교대상인 문자열(cur)과 자른 문자열(tmp)와 다르다면 그 문자열을 큐에 담아 다시 비교한다. 만약 같다면 개수를 증가시켜준다.

 

큐에 대한 반복문이 다시 실행되기 전에 비교했던 문자열의 개수와 길이를 이용하여 만들어질 문자열의 길이를 누적해준다. (aaa -> 3a라면 그냥 2를 누적해준다, 문자열을 직접 새로 만들어 마지막에 그 사이즈를 갱신시켜줘도 되겠지만, 그냥 길이만 생각해줘도 된다.)

 

이를 반복하여 자를 길이를 1씩 늘려주며 다시 반복하고 answer에 최솟값을 갱신한다.  

 

최근 풀이

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(string s) {
    int answer = s.size();
    int len = 1;    // 자를 길이
    while(len <= s.size() / 2){
        int tmp = 0;    // 현재 탐색중인 문자열의 길이
        string cur = s.substr(0,len);// 현재 기준 문자열
        int l = len, cnt = 1;
        while(1){
            if(cur == s.substr(l,len))cnt++;
            else{
                if(cnt==1)tmp+=len;
                else tmp += to_string(cnt).size() + len;
                cur = s.substr(l,len);
                cnt = 1;
            }
            if(l+len>=s.size()){
                if(cnt==1)tmp+=s.size() - l;
                else tmp += to_string(cnt).size() + s.size() - l;
                break;
            }
            l+=len;
        }
        answer = min(answer, tmp);
        len++;
    }
    return answer;
}

이번에는 큐를 이용하지않고 투 포인터 방식과 비슷하게 적용하였다.

 

큐 대신에 갱신되는 것은 cur, cur과 s.substr(l,len) 과 같으면 cnt를 증가시켜주고, 그렇지 않다면 cur에 새로운 문자열을 갱신시켜주고 tmp에 현재까지의 길이를 누적시켜준다.

 

예전풀이에서는 cnt=0부터 시작하여 비교하지 않아도 될 비교를 1번씩 더했었지만 이번에는 비교 대상 자체는 비교할 필요없이 그냥 cnt=1부터 시작하여 풀이하였다.

 

그리고 if(l+len>=s.size())이 부분은 자를길이(len)으로 모두 자르고 남은 부분 (len 보다 짧은 길이가 남았을 때)를 처리해주는 부분이다.

 

예전 풀이	최근 풀이

최근 풀이가 좀 더 빠를거라고 생각했는데, 예전 풀이가 조금 더 빠른 것 같다. 또 모든 테케에 대해 예전풀이가 더 빠르지도 않다. 흠.. 왜일까...

 

소스코드 : Python

c++ 최근 풀이와 같다.  

def solution(s):
    answer = len(s)
    for i in range(1, len(s)//2 + 1):
        cur = s[0:i]
        cnt = 1
        l = i
        tmp = 0
        while 1:
            next_str = s[l:l+i]
            if next_str == cur: cnt+=1
            else:
                if cnt!=1: tmp+=len(str(cnt))
                tmp += i
                cur = next_str
                cnt = 1
            
            if l+i>=len(s):
                if cnt!=1: tmp += len(str(cnt))
                tmp += len(s) - l
                break
            l+=i
        answer = min(answer, tmp)

    return answer