문제 소개
어피치가 문자열을 압축하려고 한다. 이때 압축하여 표현한 최소의 문자열을 구하여라.
문자열 압축은 특정한 숫자 단위로 맨 앞에서부터 행한다.
예를 들어서 문자열 aabbaccc가 있다고 하자. 이때 1개로 문자열을 압축한다고 하면 2a2ba3c가 될 것이다. 즉, 압축하려는 문자열의 숫자 기준으로 잘랐을 때 해당 문자열이 얼마나 나왔는지를 확인하는 것이다.
또 다른 예를 들어 문자열 ababcdcdababcdcd가 있다고 하자. 해당 문자열을 2개 단위로 압축하면 2ab2cd2ab2cd가 될 수 있다. 그러나 해당 문자열을 4개 단위로 압축한다고 하면 2ababcdcd가 된다. 그러므로 이때가 가장 짧은 문자열이 되고 답은 9가 된다.
문제 풀이
첫 번째 접근
일단 문자열을 나눌 수 있는 최대의 범위는 '문자열의 길이'/2라고 생각했다. 문자열의 최대 길이가 1,000개로 비교적 짧으므로 단순한 반복문으로 풀어도 무리 없다고 판단했기에 1부터 나눌 수 있는 최대 범위까지를 모두 돌려줬다.
첫 번째 반복문에서는 처음 기준이 되는 문자열 arr 을 구한다. 만일 단위를 2로 나누고 싶으면 arr은 기존 문자열의 0부터 1이 될 것이다. 만일 단위를 4로 나누고 싶다면 arr은 기존 문자열의 0부터 3까지가 될 것이다.
그리고 나서 두 번째 반복문을 작성한다. 새로운 배열 tmp의 첫 인덱스는 arr의 첫 인덱스를 따르고 tmp의 마지막 인덱스는 arr의 마지막 인덱스에 i(나눌 문자열의 단위)를 더해준 것이다.
이때 중요한 것이 있는데, tmp의 마지막 인덱스가 기존 문자열의 길이를 넘으면 안 되는 것이다. 예를 들어 기존 문자열의 길이가 5일때, 문자열을 3개씩 나눈다고 생각해보자. 그렇다면 0부터 2까지는 충분히 가능하나 3부터 5까지는 불가능하다. 왜냐하면 문자열의 길이가 5라도 배열은 0부터 시작하기 때문에 실제 인덱스는 0부터 4까지만 존재하기 때문이다.
만일 마지막 인덱스가 범위 안에 없다면 두 번째 반복문을 탈출해야 한다.
그렇지 않고 범위 안에 있다면 tmp를 주어진 인덱스만큼 잘라서 arr과 비교를 한다. 만일 두 값이 같다면 count에 1을 더해주고 다르다면 문자열의 길이를 구해줘야 한다. count가 1이라는 의미는 arr이 오로지 하나만 있다는 의미이므로 arr의 길이만을 더한다. count가 1이 아니라면 count의 길이만큼 더해주고 arr의 길이를 구한다. tmp와 arr이 다르다는 의미는 새롭게 비교할 것이 필요하다는 의미이므로 arr에 tmp를 넣어주고 count를 1로 초기화한다.
두 번째 반복문 까지 완성했다고 생각해서 끝내버리면 답이 안 나온다. 왜냐하면 맨 마지막에 있는 배열은 비교룰 해주지 않았기 때문이다. 위의 예시처럼 기존 문자열이 5이고 3으로 나눈다고 생각해보자. 그렇다면 0부터 2까지는 검사를 하지만 3부터 4까지는 범위를 벗어난다고 판단해 검사를 하지 않는다. 그러므로 해당 문자열도 검사를 해야 한다. 나는 이 부분을 제대로 고려하지 못해 시간을 너무 많이 사용했다.
여기서 tmp는 시작 인덱스부터 끝까지이다. 만일 tmp가 arr과 같다면 count에 1을 더해고 해당 count의 길이와 arr의 길이를 더해주면 된다. 어차피 tmp와 arr이 같다고 했으므로 arr의 길이에 tmp의 길이를 넣어줘도 상관 없다.
tmp와 arr이 다르다면 어찌할 것인가. 이때는 count가 1이라면 arr이 혼자 있다는 의미이므로 arr의 길이를 더한다. 여기서 arr의 길이를 더해주는 이유는 맨 마지막 부분이 고려되지 않은 채 짤렸을 경우 비교하는 값인 arr또한 길이에 고려가 안 되어 있기 때문이다.
예를 들어 arr이 abc이고 tmp가 aa라고 해보자. 이렇게 된 이유는 2번째 반복문에서 만들 새로운 배열의 길이가 기존의 배열 수를 초과했기 때문이다. 그렇기에 두 번째 인덱스에서 arr과 tmp를 비교해 arr의 길이를 넣어야 하는데, 이것이 되지 않았으므로 두 번째 배열을 벗어나서 arr의 길이와 tmp의 길이를 고려해 주는 것이다.
count가 1이 아니라면 count의 길이와 arr의 길이를 더한다. 그리고 맨 마지막으로 공통된 tmp의 길이를 더해주면 된다.
이렇게 한 후 기존의 최솟값과 새로 만든 값을 비교해서 더 작은 값을 갱신해주면 된다.
코드
파이썬
def solution(s):
answer = 0
length = len(s)//2
lengthMin = len(s) # 문자열을 하나씩만 자를 수 밖에 없다고 했을 때
if len(s) == 1:
return 1
for i in range(1, length+1):
start = 0
last = start+i
arr = s[start:last]
count = 1
lengthTmp = 0
tmp = ""
while True:
start = last
last += i
if last >= len(s):
break
tmp = s[start:last]
if arr == tmp:
count += 1
else:
if count == 1:
lengthTmp += len(arr)
else:
lengthTmp += len(str(count))
lengthTmp += len(arr)
arr = tmp
count = 1
# 맨 마지막 경우의 수도 고려해줘야 한다.
tmp = s[start : ]
if tmp == arr:
count += 1
lengthTmp += len(arr)
lengthTmp += len(str(count))
else:
if count == 1:
lengthTmp += len(arr)
else:
lengthTmp += len(str(count))
lengthTmp += len(arr)
lengthTmp += len(tmp)
lengthMin = min(lengthMin, lengthTmp)
answer = lengthMin
return answer링크
https://school.programmers.co.kr/learn/courses/30/lessons/60057?language=python3#
