๋ฌธ์ ์ค๋ช
๋ฐ์ดํฐ ์ฒ๋ฆฌ ์ ๋ฌธ๊ฐ๊ฐ ๋๊ณ ์ถ์ "์ดํผ์น"๋ ๋ฌธ์์ด์ ์์ถํ๋ ๋ฐฉ๋ฒ์ ๋ํด ๊ณต๋ถ๋ฅผ ํ๊ณ ์์ต๋๋ค. ์ต๊ทผ์ ๋๋์ ๋ฐ์ดํฐ ์ฒ๋ฆฌ๋ฅผ ์ํ ๊ฐ๋จํ ๋น์์ค ์์ถ ๋ฐฉ๋ฒ์ ๋ํด ๊ณต๋ถ๋ฅผ ํ๊ณ ์๋๋ฐ, ๋ฌธ์์ด์์ ๊ฐ์ ๊ฐ์ด ์ฐ์ํด์ ๋ํ๋๋ ๊ฒ์ ๊ทธ ๋ฌธ์์ ๊ฐ์์ ๋ฐ๋ณต๋๋ ๊ฐ์ผ๋ก ํํํ์ฌ ๋ ์งง์ ๋ฌธ์์ด๋ก ์ค์ฌ์ ํํํ๋ ์๊ณ ๋ฆฌ์ฆ์ ๊ณต๋ถํ๊ณ ์์ต๋๋ค.
๊ฐ๋จํ ์๋ก "aabbaccc"์ ๊ฒฝ์ฐ "2a2ba3c"(๋ฌธ์๊ฐ ๋ฐ๋ณต๋์ง ์์ ํ๋ฒ๋ง ๋ํ๋ ๊ฒฝ์ฐ 1์ ์๋ตํจ)์ ๊ฐ์ด ํํํ ์ ์๋๋ฐ, ์ด๋ฌํ ๋ฐฉ์์ ๋ฐ๋ณต๋๋ ๋ฌธ์๊ฐ ์ ์ ๊ฒฝ์ฐ ์์ถ๋ฅ ์ด ๋ฎ๋ค๋ ๋จ์ ์ด ์์ต๋๋ค. ์๋ฅผ ๋ค๋ฉด, "abcabcdede"์ ๊ฐ์ ๋ฌธ์์ด์ ์ ํ ์์ถ๋์ง ์์ต๋๋ค. "์ดํผ์น"๋ ์ด๋ฌํ ๋จ์ ์ ํด๊ฒฐํ๊ธฐ ์ํด ๋ฌธ์์ด์ 1๊ฐ ์ด์์ ๋จ์๋ก ์๋ผ์ ์์ถํ์ฌ ๋ ์งง์ ๋ฌธ์์ด๋ก ํํํ ์ ์๋์ง ๋ฐฉ๋ฒ์ ์ฐพ์๋ณด๋ ค๊ณ ํฉ๋๋ค.
์๋ฅผ ๋ค์ด, "ababcdcdababcdcd"์ ๊ฒฝ์ฐ ๋ฌธ์๋ฅผ 1๊ฐ ๋จ์๋ก ์๋ฅด๋ฉด ์ ํ ์์ถ๋์ง ์์ง๋ง, 2๊ฐ ๋จ์๋ก ์๋ผ์ ์์ถํ๋ค๋ฉด "2ab2cd2ab2cd"๋ก ํํํ ์ ์์ต๋๋ค. ๋ค๋ฅธ ๋ฐฉ๋ฒ์ผ๋ก 8๊ฐ ๋จ์๋ก ์๋ผ์ ์์ถํ๋ค๋ฉด "2ababcdcd"๋ก ํํํ ์ ์์ผ๋ฉฐ, ์ด๋๊ฐ ๊ฐ์ฅ ์งง๊ฒ ์์ถํ์ฌ ํํํ ์ ์๋ ๋ฐฉ๋ฒ์ ๋๋ค.
๋ค๋ฅธ ์๋ก, "abcabcdede"์ ๊ฐ์ ๊ฒฝ์ฐ, ๋ฌธ์๋ฅผ 2๊ฐ ๋จ์๋ก ์๋ผ์ ์์ถํ๋ฉด "abcabc2de"๊ฐ ๋์ง๋ง, 3๊ฐ ๋จ์๋ก ์๋ฅธ๋ค๋ฉด "2abcdede"๊ฐ ๋์ด 3๊ฐ ๋จ์๊ฐ ๊ฐ์ฅ ์งง์ ์์ถ ๋ฐฉ๋ฒ์ด ๋ฉ๋๋ค. ์ด๋ 3๊ฐ ๋จ์๋ก ์๋ฅด๊ณ ๋ง์ง๋ง์ ๋จ๋ ๋ฌธ์์ด์ ๊ทธ๋๋ก ๋ถ์ฌ์ฃผ๋ฉด ๋ฉ๋๋ค.
์์ถํ ๋ฌธ์์ด s๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ์์ ์ค๋ช ํ ๋ฐฉ๋ฒ์ผ๋ก 1๊ฐ ์ด์ ๋จ์๋ก ๋ฌธ์์ด์ ์๋ผ ์์ถํ์ฌ ํํํ ๋ฌธ์์ด ์ค ๊ฐ์ฅ ์งง์ ๊ฒ์ ๊ธธ์ด๋ฅผ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์.
์ ํ์ฌํญ
์ ์ถ๋ ฅ ์
s | result |
---|---|
"aabbaccc" | 7 |
"ababcdcdababcdcd" | 9 |
"abcabcdede" | 8 |
"abcabcabcabcdededededede" | 14 |
"xababcdcdababcdcd" | 17 |
์
์ถ๋ ฅ ์์ ๋ํ ์ค๋ช
์
์ถ๋ ฅ ์ #1
๋ฌธ์์ด์ 1๊ฐ ๋จ์๋ก ์๋ผ ์์ถํ์ ๋ ๊ฐ์ฅ ์งง์ต๋๋ค.
์ ์ถ๋ ฅ ์ #2
๋ฌธ์์ด์ 8๊ฐ ๋จ์๋ก ์๋ผ ์์ถํ์ ๋ ๊ฐ์ฅ ์งง์ต๋๋ค.
์ ์ถ๋ ฅ ์ #3
๋ฌธ์์ด์ 3๊ฐ ๋จ์๋ก ์๋ผ ์์ถํ์ ๋ ๊ฐ์ฅ ์งง์ต๋๋ค.
์ ์ถ๋ ฅ ์ #4
๋ฌธ์์ด์ 2๊ฐ ๋จ์๋ก ์๋ฅด๋ฉด "abcabcabcabc6de" ๊ฐ ๋ฉ๋๋ค.
๋ฌธ์์ด์ 3๊ฐ ๋จ์๋ก ์๋ฅด๋ฉด "4abcdededededede" ๊ฐ ๋ฉ๋๋ค.
๋ฌธ์์ด์ 4๊ฐ ๋จ์๋ก ์๋ฅด๋ฉด "abcabcabcabc3dede" ๊ฐ ๋ฉ๋๋ค.
๋ฌธ์์ด์ 6๊ฐ ๋จ์๋ก ์๋ฅผ ๊ฒฝ์ฐ "2abcabc2dedede"๊ฐ ๋๋ฉฐ, ์ด๋์ ๊ธธ์ด๊ฐ 14๋ก ๊ฐ์ฅ ์งง์ต๋๋ค.
์ ์ถ๋ ฅ ์ #5
๋ฌธ์์ด์ ์ ์ผ ์๋ถํฐ ์ ํด์ง ๊ธธ์ด๋งํผ ์๋ผ์ผ ํฉ๋๋ค.
๋ฐ๋ผ์ ์ฃผ์ด์ง ๋ฌธ์์ด์ x / ababcdcd / ababcdcd ๋ก ์๋ฅด๋ ๊ฒ์ ๋ถ๊ฐ๋ฅ ํฉ๋๋ค.
์ด ๊ฒฝ์ฐ ์ด๋ป๊ฒ ๋ฌธ์์ด์ ์๋ผ๋ ์์ถ๋์ง ์์ผ๋ฏ๋ก ๊ฐ์ฅ ์งง์ ๊ธธ์ด๋ 17์ด ๋ฉ๋๋ค.
๋ฌธ์ ํ์ด
์ฒซ๋ฒ์งธ ํ์ด
def solution(s):
w = ""
count = 1
answer = ""
for i in s:
if w == i:
count += 1
else:
if w != "":
if count == 1:
answer += w
else:
answer += str(count)+w
w = i
count = 1
if count == 1:
answer += w
else:
answer += str(count)+w
return len(answer)
#๋จผ์ ํ๊ธ์ ๋จ์๋ก ๋๋ ์๊ณ ๋ฆฌ์ฆ ๊ตฌํ
๋๋ฒ์งธ ํ์ด
def solution(s):
if len(s) == 1:
return 1
answer = []
w = ""
for i in range(1, len(s)):
count = 1
word = s[:i] #๋ฌธ์์ด ๊ธธ์ด ๋๋๊ธฐ
for j in range(i, len(s), i):
#i๋ถํฐ ์์ํด์ i๋งํผ์ ์คํ
์ผ๋ก ๋ฒ์๋ฅผ ๋ง๋ ๋ค
if s[j:j+i] == word: #์๋ฆฐ ๋ฌธ์์ด๊ณผ ๋ค์ ๋ฌธ์์ด์ด ๊ฐ๋ค๋ฉด
count += 1
else:
if count == 1: #์๋ฆฐ ๋ฌธ์์ด์ count ๋ฆฌ์
count = ""
w += str(count)+word #ํด๋น ๋ฌธ์์ด์ w์ ๋ณด๊ด
word = s[j:j+i] #๋ค์ ๋ฌธ์์ด ์์
count = 1
if count == 1: #๋ง์ง๋ง ๋ฐ๋ณต๋๋ ๋ฌธ์์ด์๋ํ ์๋ต๋๋ฌธ์ ์์ ์กฐ๊ฑด๋ฌธ๊ณผ ๋์ผํ๊ฒ ์ถ๊ฐ
count = ""
w += str(count)+word
answer.append(len(w))
w = "" #๋จ์ ๋ฌธ์์ด์ ์ฌ์์์ํด ์ด๊ธฐํ
return min(answer)
๋ค๋ฅธ ์ฌ๋ ํ์ด
def compress(text, tok_len):
words = [text[i:i+tok_len] for i in range(0, len(text), tok_len)]
res = []
cur_word = words[0]
cur_cnt = 1
for a, b in zip(words, words[1:] + ['']):
if a == b:
cur_cnt += 1
else:
res.append([cur_word, cur_cnt])
cur_word = b
cur_cnt = 1
return sum(len(word) + (len(str(cnt)) if cnt > 1 else 0) for word, cnt in res)
def solution(text):
return min(compress(text, tok_len) for tok_len in list(range(1, int(len(text)/2) + 1)) + [len(text)])