[ programmers ] DFS/BFS - 문자열 압축

문제 링크

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

문제설명

파라메터로 주어진 문자열 s를 문자열의 시작부터 n개 단위로 잘라 압축했을때, 압추된 문자열 중 가장 짧은 것의 길이

문제풀이

시도 1

문자열을 1개단위부터 len(s)//2+1개 단위까지 잘라서 리스트에 넣은 후 각각 비교를 하려고 했다.

def solution(s):
    length = len(s)
    answer = length
    
    for l in range(1, length//2+1):
        compressed = ""
        count = 1
        #주어진 문자열을 1개부터 length//2개단위로 자르기
        lst = [s[i:i+l] for i in range(0, len(s), l)]
        
				#
				#
				#
    return answer

자르는거 까지는 어찌 완료했는데 리스트내에서 같은 문자열을 비교할 방법이 생각나지 않았다. for문을 돌려면 압축가능한 원소를 pop할수도 없고,, 압축가능한 원소를 -1따위로 치환해놔도 어차피 다시 확인하러 돌면서 같은 문제가 발생하고 ,,?? 모르겠어서 답을 봤다

정답 코드

def solution(s):
    length = len(s)
    answer = length
    
	#1개 단위부터 압축단위를 늘려가면서 확인하기
    for step in range(1, length//2+1):
        compressed = ""
        count = 1
        prev = s[0:step]

		#단위 크기만큼 증가시키며 이전 문자열과 비교 
        for j in range(step, len(s), step):
            if prev == s[j:j+step]:
                count += 1
		#더이상 압축하지 못하는 경우
            else:
                compressed += str(count) + prev if count >= 2 else prev
		#상태 초기화
                prev = s[j:j+step]
                count = 1

	#남은 문자열에 대해 처리
        compressed += str(count) + prev if count >= 2 else prev
        answer = min(answer, len(compressed))

    return answer

이 코드는 먼저 인풋으로 들어온 문자열을 잘라 리스트에 넣고 비교하려고 했던 나와 다르게 for문을 돌면서 매번 잘라서 비교를 하였다. 그리고 리스트 내에서 같은 문자열을 비교해서 조작하려고 했던 나와 다르게 compressed라는 문자열을 선언해 압축한 결과를 따로 저장했다.

포인트

• 이전 문자열을 따로 저장해서 비교
• 압축 결과를 append하여 따로 저장

시도 2

def solution(s):
    length = len(s)
    answer = length
    
    for l in range(1, length//2+1):
        compressed = ""
        count = 1
        lst = [s[i:i+l] for i in range(0, len(s), l)]
        prev = lst[0]

        for i in range(1, len(lst)):
            if prev == lst[i]:
                count += 1
            else:
                compressed += str(count) +prev if count>=2 else prev
                count = 1
                prev = lst[i]
                print(compressed)

        compressed += str(count) +prev if count>=2 else prev
        answer = min(answer, len(compressed))

    return answer

정답을 보고 중복되는 문자열을 비교하는 부분을 다시 짜보았다.

어렵네 ~ 다음주쯤에 다시 한번 풀어봐야겠다.

오늘 알게 된 것

• 문자열을 n개 단위로 잘라서 리스트에 저장하기

  lst = [s[i:i+l] for i in range(0, len(s), l)]

• if문 한줄에 쓰기

  compressed += str(count) +prev if count>=2 else prev