프로그래머스 2020 KAKAO BLIND RECRUITMENT 코딩테스트에서 출제된 문제
분석
문자열 "aabbaccc"을 처음부터 시작하여 이를 n개 단위로 압축
- 3개 단위 -> aabbaccc (압축되지 않는다)
- 2개 단위 -> aabbaccc (압축되지 않는다)
- 1개 단위 -> 2a2ba3c
n개의 단위로 압축하였을 때 가장 짧은 문자열의 길이를 return한다
문자열을 이 정도로 만져본적이 없어서 막막했던 문제
1. answer는 문자열의 길이로 초기화
문자열 "abcdefg"
- n=3 abc def g (압축이 되지않는다)
- n=2 ab cd ef g (압축이 되지 않는다)
- n=1 a b c d e f (압축이 되지 않는다)
n단위로 잘랐을때의 모든 상황에서 압축이 가능하지 않다면 answer는 문자열의 길이가 되기 때문에 answer의 초기값은 문자열의 길이가 된다.
2. 단위는 (문자열 길이)//2부터 시작하여 1까지
문자열 "ababcdcdababcdcd"의 길이는 16이다
- 16//2인 8단위로 압축
n=8 ababcdcd ababcdcd => 2ababdcdc로 압축이 된다- 9단위로 압축
n=9 ababcdcda babcdcd (압축이 되지 않는다)
문자열을 압축할때 가장 큰 단위가 n//2가 된다. 문자열의 길이가 16일경우에 9단위로는 절대 자를 수 없기 때문이다. (16//2인 8단위부터 가능)
자를 수 있는 가장 작은 단위인 1단위까지 압축한다.
3. 문자열 검색하고 카운트 후 n만큼 인덱스 이동
압축 가능한 문자열이 있으면 압축하고 난 뒤에 탐색할 문자의 위치는 (압축한 카운트)*(n 단위)만큼 뒤로 이동해주면 그 뒤에 탐색할 문자에 자리 잡고 있을 것이다.
압축 가능한 문자열이 아니라면 n 단위만큼 뒤로 이동해주면 된다
(python의 for 문에서 인덱스 이동이 안 되는 것인지 못하는 것인지 while 문을 사용하여 인덱스 조작을 하였다)
4. 문자열 시작하는 부분
문자열 "xababcdcdababcdcd"
- 8단위로 압축을 진행할 경우에
n=8 x ababcdcd ababcdcd => 이렇게는 되지 않는다
n=8 xababcdc dababcdc d (압축이 되지 않는다)
문자열을 n단위로 자를때 시작점은 0에서 시작한다. 그렇기 때문에 위의 문자열은 x로 시작하기 때문에 어떤 단위로 하여도 현재보다 더 작은 값으로 압축될 수 없다
코드
def solution(s):
answer = len(s) # ①
for n in range(len(s)//2,0,-1): # ②
string, j = '', 0
while j<len(s):
start, end = j, j+n
tmp = s[start:end]
cnt=1
while tmp==s[start+n:end+n]: # 문자열이 다음 문자열과 같다면
start+=n
end+=n
cnt+=1
if cnt==1:
string+=s[j:j+n]
j+=n # ③ 1개이므로 n단위만큼 뒤로
else:
string+=str(cnt)+tmp
j+=cnt*n # ③ 여러개이므로 n*(cnt)만큼 뒤로
answer = min(answer, len(string))
return answer처음 문제를 읽었을때 겁을 먹을 수 밖에 없는 지문 길이, 어떻게 해야될지 모르겠는 막막함 만 있던 문제다.
모든 상황을 탐색해야겠다는 생각이 들었고 생각을 그대로 코드로 작성하였다. 도중에 나오는 값들을 계속 확인하고 이를 진행하였다.
