카카오 코테 - 문자열 압축

문자열 길이로 판별하는 방식으로 풀었다.

 

정답 코드

def solution(s):
    half = len(s) // 2
    answer = 1e9
    if(len(s) == 1):
        answer = 1
    
    for i in range(1, half + 1):
        base = s[0:i]
        count = 1
        temp = 0
        for j in range(i, len(s), i):
            current = s[j:j+i]
            if base == current:
                count += 1
            else:
                temp += len(base)
                if count > 1:
                    temp += len(str(count))
                base = current
                count = 1
        temp += len(base)
        if count > 1:
            temp += len(str(count))
        answer = min(answer, temp)
    return answer

 

계속 72점 나와서 테스트 케이스 찾느라 온갖 테스트 케이스를 다 넣었는데

이분 글 보고 깨달음을 얻었다.

다 푸는데 2시간 좀 안 되게 걸렸다.

https://programmers.co.kr/questions/25102

 

잘못 생각한 풀이

분할 정복으로 왼쪽부터 계속 반씩 쪼개면 되지 않을까 싶었지만,

abcdabcdaa 같이 끝에 더미 문자열이 붙어 있으면 abcda / bcdaa 가 되버려

분할 정복 문제는 아니라고 생각했다.

 

문자열 길이로 판별하기

처음 묶여지는 문자열 길이만큼 묶인다고 했으니,

문자가 1개씩 묶일 때 부터, 전체 문자열의 반까지 묶이는 경우를 생각했다.

마침 s의 최대 길이가 1,000이니 O(N ^ 2)은 1,000,000으로 시간 초과 걱정은 없었다.

문자열 길이가 1인 경우는 사전에 검사해 1로 리턴했다.

 

포문 조건식은 다음과 같다.

i : 1 ~ 문자열 절반 + 1

j : i ~ 문자열 전체 길이, i 만큼 증가

 

여기서 i의 종료 조건에 + 1을 해준 이유는

문자열 s의 길이가 8이라면 i는 1~4까지 돌아야 하기 때문이다.

 

첫 포문에서 s의 첫 번째 인덱스 부터 길이 i 만큼 슬라이싱 한 문자열을 base라고 정한다.

두 번째 포문에서 이후 문자열들을 슬라이싱한 걸 current라고 정한다.

 

base == current라면

카운팅을 1 늘려주고

 

bae != current라면

문자열 base 길이를 임시 변수 temp이 더해준다.

만약, count 가 2 이상이면, count의 자릿수 만큼 temp에 더한다.

 

base를 current 로 바꾼 뒤, count 역시 1로 바꿔준다.
(0으로 해도 되지만, 디버깅 하기 편하게 1부터 시작했다)

 

두 번째 포문이 끝났다면, 마찬가지로

count 횟수를 보고 temp에 다한다.

aaaaaaa의 경우 카운팅만 돼서 두 번째 포문을 빠져나가기 때문.

 

이렇게 temp와 answer(초기값 : 1e9)의 최소값을 비교해 answer에 넣고 반환하면 끝.

 

 

중요한 부분

위에 설명해서 굵게 표시한 부분이 있다.

 -> 만약, count 가 2 이상이면, count의 자릿수 만큼 temp에 더한다. <-

 

처음에 문자열 압축되는 횟수를 2, 3 정도로 생각해

count가 2 이상이면 temp + 1로 처리하다 계속 72점이 나오는 문제가 생겼다.

알고보니 count가 10 이면 temp + 2를 해줘야 했다.

따라서, count의 자릿수 만큼 temp에 더해줘야 한다.

 

이 부분을 생각 못하다 1시간 정도 허비했다..