[2020 카카오 공채] 문자열 압축

문자열 압축

 

---

Problem?

문제 링크 : [2020 카카오 공채] 문자열 압축

프로그래머스

 

Solution

구현 문제

비교하는 문자열의 길이를 해당 문자열의 크기의 반부터 1까지 반복하며 문자열을 단순 비교한다.

"비교하는 문자열의 길이"가 끝에 도달하기 전까지 반복한다.

특이사항으로 반복되는 횟수가 10번 이상인 경우 자릿수를 고민해줘야 한다.

 

가정 getSize() : 자릿수를 구하는 함수 solution() : 문제 해결 코드   slen : 전체 문자열의 길이 len : 비교하는 문자열의 길이 start_pos : 문자열을 비교하는 위치 cnt : 반복 여부 확인

Code(핵심 코드)

int solution(string s) {
	int slen = s.length();
	int ans = slen;
	
	// len--
	for (int len = slen / 2; len > 0; len--) {
		int start_pos = 0;
		int t_len = slen;
		int cnt = 0;

		while (start_pos + len <= slen) {
			// if sub string is same pattern
			if (s.substr(start_pos, len).compare(s.substr((start_pos + len), len)) == 0) {
				cnt++;
			}
			else {
				if (cnt >= 1) {
					t_len -= (cnt * len);		    // delete same pattern
					t_len += getSize(cnt + 1);	// add num, +1 is (I'm not count original key)
				}
				cnt = 0;
			}
			start_pos += len;
		}
		ans = min(ans, t_len);
	}
	return ans;
}

 

---

쉬웠던 구현 문제.

아이디어가 중요할 것 같다.

 

* 문제 있을 시 삭제하겠습니다.