on1ystar 머릿속을 정리, 기록하는 곳

<2020 KAKAO BLIND RECRUITMENT-python> 문자열 압축

11 Feb 2021


시간 제한 : 1초

메모리 제한 : 128 MB

출처 : programmers 코딩테스트 연습 - 문자열 압축


문제 요약

어피치는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다.

예를 들어, ababcdcdababcdcd의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 2ab2cd2ab2cd로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 2ababcdcd로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.

압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.


제한사항

  • s의 길이는 1 이상 1,000 이하입니다.
  • s는 알파벳 소문자로만 이루어져 있습니다.

(자세한 사항은 위 문제 링크 참고)


내가 적어본 문제 풀이

필수적으로 주어진 문자열을 탐색해야 하는데, 그 방법으로 2가지를 생각했다. 첫째는 문자열을 스택에 넣어 꺼내보면서 이전 문자열과 같은 지 탐색하는 방법과, 파이썬 리스트의 인덱스 슬라이싱을 이용해 탐색하는 방법이다.

파이썬의 장점을 이용하기 위해 두 번째 방법을 이용했다.

먼저 탐색하기 전에 문자열을 압축할 단위만큼 탐색해야 하므로 탐색 단위의 범위를 지정한다.

  • 최소 단위 : 1
  • 최대 단위 : 전체 문자열의 길이 / 2

탐색할 문자열의 길이를 1부터 최대 단위인 s의 절반 길이까지 모두 탐색한다. 즉, 완전 탐색을 해야하는데, 이유는 아래 예시를 보면 알 수 있다.

#1 문자열을 1개 단위로 잘라 압축했을 때 가장 짧음
>>> s = "aabbaccc"
7

#2 문자열을 8개 단위로 잘라 압축했을 때 가장 짧음
>>> s = "ababcdcdababcdcd"
9

위 예시에서 첫 번째 예시는 문자열을 2개 단위로 압축할 수 있음에도 1개 단위로 잘라 압축했을 때 가장 짧다.

반면, 두 번째 예시는 최대 단위인 8개 단위로 잘라 압축했을 때 가장 짧다.

주어진 문자열을 가장 짧게 압축하는 방법론이 없기 때문에 완전 탐색을 해 가장 짧은 경우의 수를 찾아야 한다. 따라서 최소 단위부터 최대 단위까지 반복한다.

max_slice_len = len(s) // 2
	slice_len = 1
	min_compression_len = len(s)
	while slice_len <= max_slice_len:
		pre_slice = ""
		duplicate_cnt = 1
		compression_s = ""
		# for...
		slice_len += 1

이제 slice_len단위만큼 문자열 s를 탐색하면서 중복된 문자열을 압축해 compression_s에 넣어준다.

# ...
	for i in range(0,len(s),slice_len):  # s 인덱스를 slice_len 만큼 건너 뛰면서
	    if i+slice_len <= len(s):  # s 인덱스 초과 검사
	        now_slice = s[i:i + slice_len]
	        if pre_slice == "":  # 첫 문자열 초기화
	            pre_slice = now_slice
	        elif pre_slice == now_slice:  # 압축할 문자열을 찾은 경우
	            duplicate_cnt += 1
	        else:
	            if duplicate_cnt != 1:  # 압축할 문자열이 있는 경우
	                compression_s += str(duplicate_cnt) + pre_slice
	            else:
	                compression_s += pre_slice
	            pre_slice = now_slice
	            duplicate_cnt = 1
	    else:  # s 인덱스 초과 시 남은 자투리 문자열 합치기
	        now_slice = pre_slice + s[i:]
	if duplicate_cnt != 1:
	    compression_s += str(duplicate_cnt) + now_slice
	else:
	    compression_s += now_slice
	if min_compression_len > len(compression_s):
	    min_compression_len = len(compression_s)
# ...

range(0,len(s),slice_len)를 사용하면 0부터 len(s)까지 slice_len만큼 건너 뛰며 순회한 값을 리턴해 i에 담아 준다.

이를 이용해 s[i:i+slice_len]씩 탐색하며 압축할 문자열을 검사한다. 단, i+slice_len가 s의 인덱스를 초과한 경우는 마지막 문자열 길이가 slice_len보다 작은 것이므로 따로 예외처리를 해준다.

그리고 for가 1회 순환을 마친 뒤, 마지막에 검사했던 문자열 압축 처리를 따로 해줘야 한다.

전체 코드 → https://github.com/on1ystar/algorithm-problem-solving-codes/blob/master/Implementation/문자열 압축.py

Related posts