[프로그래머스] 문자열 압축

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

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

 

 

<문제 설명>

문자열을 압축하고자 한다.

 

예1) 문자열 "aabbaccc"로 예를 들어보자.

문자를 1개 단위로 잘랐을 때 "2a2ba3c"로 7자리가 된다.

2개 단위로 잘랐을 때는 "aabbaccc"로 8자리가 된다.

3개 단위로 잘랐을 때는 "aabbaccc"로 마찬가지로 8자리다.

이런 식으로 1개 이상의 문자를 잘라서 압축한다.

 

예2) "abcabcabcabcdededededede"

문자를 1개 단위로 자르면 "abcabcabcabcdededededede"

2개 단위로 자르면 "abcabcabcabc6de"

3개 단위로 자르면 "4abcdededededede"

4개 단위로 자르면 "abcabcabcabc3dede"

6개 단위로 자르면 "2abcabc2dedede"

 

이렇게 문자열을 압축해서 가장 짧은 문자열의 길이를 출력하는 문제이다.

 

 

 

<문제 이해>

먼저 문자열을 자르는 것이 우선이라고 생각했다.

자르는 단위는 1부터 (문자열의 길이)/2개의 단위면 될 것이라고 생각했고,

잘라진 문자열끼리 비교해 문자의 길이를 줄여나가면 된다고 생각했다.

예를 들어 abc / abc / dbd 라고 하면 첫번째 abc와 두번째 abc를 비교하고 두번째 abc와 dbd를 비교해각각 필요한 처리를 해주는 것이 좋겠다고 생각했다. 그렇지만 그 필요한 처리를 생각해내는 데에는 시간이 오래 걸렸다,,,,

 

 

 

<문제 풀이>

import math

def solution(s):
    min = len(s)			# 초기값은 최댓값 할당 => 문자열의 길이
    
    for i in range(1,int(len(s)/2)+1):		# 문자열의 단위인 i는 1부터 (문자열 길이)/2
        temp = len(s)				# 각 단위마다 길이를 알아내기 위함.
        flag = 0				# flag는 이전과 같은 문자열이였는지, 몇번 반복되는지 확인하기 위한 변수
        
        for j in range(0,len(s),i):		# 길이가 i인 문자열을 보기 위한 range 설정
            if s[j:j+i] == s[j+i:j+i*2]:	# j번째 인덱스의 문자열과 j+i번째 인덱스의 문자열이 같다면
                if(flag==0): 			# 이전에 문자열이 없거나, 그 문자열과 다른 문자열이라면
                    flag = 1			# 현재 문자열 두개가 같으니까 일단 flag=1
                temp -= i			# 문자열의 길이에서 i만큼을 빼준다
                flag += 1			# flag에 1을 더해주는 이유는 같은 문자열이 몇번 나오는지 알기 위함
            
            else :						# 문자열이 같지 않다면
                if flag != 0:					# flag가 0이 아닐때 => 반복되던 문자열이 끝났을 때를 의미
                    temp = temp + int(math.log10(flag))+1	# 반복된 만큼의 자리수를 temp에 더함
                    flag = 0					# flag 초기화
                
        if(min > temp) : min = temp  		# temp의 길이가 더 작으면 min 교체
            
    return min

 

문자열을 자르고 비교하는 데까지는 수월하게 했지만

반복된 문자열을 어떻게 카운트해야할지에 대해서 많이 고민했다.

생각해낸 방법은 flag를 사용하는 방법이었다.

 

flag는 이전 문자열과 현재 문자열이 같은지를 알려주는 변수이며, 몇 번 반복되었는지를 나타내는 변수이다.

예를 들어 abc / abc / dbd 이고, 비교 전이면 flag는 0의 값을 가진다.

abc와 abc는 같고, 현재 flag가 0이기 때문에 flag를 1로 바꾸어주었다. 

그리고 temp의 값을 단위의 길이만큼을 빼주고, flag에 1을 더한다.

여기서 flag에 1을 또 더하는 이유는 몇 번 반복되었는지를 알기 위해서이다. 

 

또한, 한자리수만큼 반복되는 경우만 있는게 아니라 100번 1000번 반복될수 있기 때문에

flag에 계속 더해질 수 있도록 했고, 마지막에 log를 이용해 flag의 자리수를 구했다.

(처음에 이거 고려 안해줬다가 틀렸다)

 

그리고 abc와 dbd를 비교한다. 두 문자열은 다르기 때문에 else문으로 가게된다.

이때 flag는 2의 값을 가지므로 temp에 flag의 자리수인 1이 더해지고 flag를 다시 초기화한다.

 

이렇게 하면 3개 단위로 나눈 abcabcdbd는 2abcdbd가 되고 압축된 문자열의 길이는 7이 된다.

 

사실 압축된 문자열을 출력하라는 문제가 아니였기 때문에 압축된 문자열이 어떻게 생겼는지는 알 수 없는 코드이다.

단순히 문자열의 길이만 구할 수 있도록 코드를 작성했다 : )

 

 

 

<실행 결과>

 

 

 

 

레벨 2인데 너무 시간을 많이 썼다,,,

레벨 3은 어떻게 풀려고,,,,,,,,,,,

그래도 푼 것에 의의를 둔다ㅎㅎ