[2020 KAKAO BLIND] 문자열 압축 / 사용언어 : 파이썬(python)

※ 문제링크

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

※ 관련개념

Sliding Window

해당문제는 투 포인터와 슬라이딩 윈도우의 개념을 활용해서 풀 수 있는 문제였다. 문제의 조건 중에 처음 문자열부터 기준으로 정해진 길이만큼 슬라이싱을 해야한다고 주어졌기에 중간부터 값이 묶이는 상황을 고려하지 않아도 되었다. 알고리즘 구상 자체는 정해진 길이만큼 슬라이싱을 반복해서 비교 후 중복횟수를 카운트해서 압축 후 문자열의 상태를 만들어서 그 중에서 가장 짧은 길이를 반환하면 되는 문제였다. 슬라이싱 길이도 주어진 문자열의 절반로 작성하여 반복횟수를 줄여주었으며, 자세한 문제풀이 방법과 코드는 아래와 같다.
1. 슬라이싱 길이에 따라 압축 후 문자열의 길이를 확인할 리스트와 슬라이싱 결과를 저장할 리스트를 만든다.
2. 포인터로 활용할 2개의 변수와 중복횟수를 체크할 변수를 선언해준다.
3. 반복문으로 슬라이싱 길이를 변경하여 수행해주고(입력문자열 길이의 절반까지만 수행), 각 경우의 값을 저장한다.
4. 모든 반복문 종료 후 입력문자열의 길이가 1이하인 경우를 고려하여 최소 길이 문자열의 길이를 출력한다.
★ 세부 코드에 보다 상세한 설명을 작성하였으니 참고바랍니다.

 

# 로직 확인용 코드(문제풀이통과 안됨)
# 주어진 문자의 길이의 절반까지만 체크 
def solution(s):
    zip_list = []
    for i in range(1, (len(s)//2)+1):
        s_check = []
        cp1, cp2 = 0, i
        cnt = 1
        while (cp2 + i) <= len(s):
            range_01 = s[cp1:cp1+i]
            range_02 = s[cp2:cp2+i]
            # print(i, cp1, cp2, cnt, range_01, range_02)
            if range_01 == range_02:
                cnt += 1
                cp2 += i
                if cp2 + i > len(s):
                    s_check.append(str(cnt) + range_01) 
            if range_01 != range_02:
                cp1 = cp2 
                cp2 = cp2 + i
                if cnt == 1:
                    s_check.append(range_01)
                    if cp2 + i > len(s):
                        s_check.append(range_02)
                else:
                    s_check.append(str(cnt) + range_01)
                    if cp2 + i > len(s):
                        s_check.append(range_02)
                cnt = 1

        
        if len(s) % i != 0:
            s_check.append(s[cp2:])
        zip_list.append(s_check)

    return zip_list
        
    # answer = 0
    # return answer

s = "x"	
solution(s)

 

# 제출 코드
# 주어진 문자의 길이의 절반까지만 체크 
# 주의점 : 입력문자열의 길이가 0 또는 1일 경우 // 중복되는 조합수가 10의 자리 이상일때
def solution(s):
    zip_list = [] # 각각의 슬라이싱 경우의 압축 후 문자열 길이를 확인할 리스트 생성
    for i in range(1, (len(s)//2)+1):
        s_check = [] # 슬라이싱 후 문자열의 길이를 체크할 리스트 생성
        cp1, cp2 = 0, i # 포인터용 변수 2개 선언
        cnt = 1 # 중복횟수 확인용 변수 선언
        while (cp2 + i) <= len(s):
            range_01 = s[cp1:cp1+i] # 슬라이싱 1
            range_02 = s[cp2:cp2+i] # 슬라이싱 2
            if range_01 == range_02: # 범위 값이 동일한 경우 조건문
                cnt += 1
                cp2 += i
                if cp2 + i > len(s): 
                    s_check.append(i+len(str(cnt))) # 중복횟수가 10번이상인 경우 고려하여 작성
            if range_01 != range_02: # 범위 값이 다를 경우 조건문
                cp1 = cp2 
                cp2 = cp2 + i
                if cnt == 1:
                    s_check.append(i)
                    if cp2 + i > len(s):
                        s_check.append(i)
                else:
                    s_check.append(i+len(str(cnt))) # 중복횟수가 10번이상인 경우 고려하여 작성
                    if cp2 + i > len(s):
                        s_check.append(i)
                cnt = 1

        if len(s) % i != 0: # 위의 반복문안에 들어가지 않은 끝의 문자열 수 체크 후 저장
            s_check.append(len(s[cp2:]))
        zip_list.append(sum(s_check))
    # 문자열의 길이가 1이하인 경우 고려
    if len(s) == 0:   
        answer = 0 
    elif len(s) == 1:
        answer = 1
    else:
        answer = min(zip_list) 
    return answer

s = ""	
solution(s)

 

P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.