[2020 Kakao Blind] 문자열 압축 (C++, python3)

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

코딩테스트 연습 - 문자열 압축 | 프로그래머스

 

시험 볼 때는 40분? 정도 걸렸던 문제인데 다시 풀려고 보니 1시간을 훌쩍 넘겨버렸다.

 

아마 긴장감 때문에 좀 더 빨리 풀지 않았나 싶다.

 

풀이 방법은 처음에 1개, 그 다음에 2개..... 식으로 while문을 2개 이용해서 완전 탐색을 돌렸다.

 

- C++ 풀이

#include <string>
#include <vector>

using namespace std;

int solution(string s) {
    int answer = 0;
    
    int range = 1;
	answer = 0x7fffffff;
	int i = 1, j = 0, k = i;

	while (1) {
		string find_str, temp = s;
		string sub_s, result;
		int cnt = 1;
		if (i > s.length()) break;

		while (1) {
			if (temp.length() == 0) break;
			if (temp.length() < i) {
				result += temp;
				break;
			}
			else {
				sub_s = temp.substr(0, i);
				find_str = temp.substr(k, i);
				temp = temp.substr(i);
			}

			if (sub_s == find_str) {
				cnt += 1;
			}
			else {
				if (cnt > 1) {
					result += to_string(cnt);
					cnt = 1;
				}
				result += sub_s;
				find_str = "", sub_s = "";
			}
		}
		i += 1, k = i;

		if (answer > result.length()) {
			answer = result.length();
		}
	}
    
    return answer;
}

 

 

- Python 풀이

def solution(s):
    answer = 0
    
    length = len(s)
    answer = 9999999

    if length == 1:
        answer = 1
    else:
        for i in range(0, length):
    
            begin = 0
            end = i + 1

            before = s[begin:end]
            temp = s[end:]

            cnt = 1
            newstr = ''

            while(temp) :
                str_cmp = temp[begin:end]
                temp = temp[end:]

                if before == str_cmp:
                    cnt += 1
                    before = str_cmp

                else:
                    if cnt > 1:
                        newstr += (str(cnt) + before)
                    else:
                        newstr += before

                    cnt = 1
                    before = str_cmp

            if cnt > 1:
                newstr += (str(cnt) + before)
            else:
                newstr += before

            newstr_length = len(newstr)
            if newstr_length < answer:
                answer = newstr_length
    
    return answer