[プログラマ]文字列の圧縮
問題の説明
データ処理の専門家になりたいarfitchは、文字列を圧縮する方法を学んでいます.最近,文字列に連続的に現れる同じ値を文字数と繰返し値として表すことによって,より短い文字列に減少する簡単な無損圧縮法を学習した.
例えば、aabacccについては、2 a 2 ba 3 c(文字が重複せず、一度しか出現せず、1を省略する)と表すことができ、この方法の欠点は、重複文字が少ない場合に圧縮率が低いことである.たとえばabcabcdedeのような文字列は圧縮されません.この欠点を解決するために、ピッチは、文字列を1つ以上の単位に切り取って圧縮し、より短い文字列として表す方法を探します.
例えば、abbcdcababcdcdの場合、文字を1単位に切り取ると全く圧縮されないが、2単位に切り取ると2 ab 2 cdとして表すことができる.異なる方法で8単位でせん断と圧縮を行う場合は、2 abbcdcdを用いて表すことができ、この場合圧縮が最も短い.
別の例はabcabcdedeであり、文字を2単位に切り取って圧縮するとabcabc 2 deであり、3単位に切り取ると2 abcdedeであり、この3単位が最も短い圧縮方法である.3つの単位を切り取り、最後に残った文字列を貼り付けます.
圧縮する文字列sをパラメータとして指定する場合は、上述した方法に従って1つ以上の単位で文字列を切り取り、solution関数を完了して、表す文字列の中で最も短い長さを返します.
せいげんじょうけん
sの長さは1または1000以下である.
sは小文字のみからなる.
I/O例
s result
"aabbaccc" 7
"ababcdcdababcdcd" 9
"abcabcdede" 8
"abcabcabcabcdededededede" 14
"xababcdcdababcdcd" 17
I/O例説明
I/O例#1
文字列を1つの単位で切り取って圧縮する場合に最も短い.
I/O例#2
文字列を8単位で切り取って圧縮する場合が最も短い.
I/O例#3
文字列を3つの単位で切り取って圧縮する場合に最も短い.
I/O例#4
文字列を2つの単位で切断すると、その文字列はabcabcabc 6 deになります.
文字列を3単位に切り取ると、4 abcdededededededeedが生成されます.
文字列を4単位に切り取るとabcabcabc 3 dedeが生成されます.
文字列を6単位で切断すると、2 abcabc 2 dedeとなり、長さは最短14となる.
I/O例#5
文字列は、先頭から指定した長さで切り捨てなければなりません.
したがって、所与の文字列をx/abbcdcd/abbcdcdに切り取ることはできない.
この場合、最も短い長さは17であり、どうしても文字列を切り取っても圧縮されないためである.
s:文字列、length:文字列長、i:トリミングする長さ単位
データ処理の専門家になりたいarfitchは、文字列を圧縮する方法を学んでいます.最近,文字列に連続的に現れる同じ値を文字数と繰返し値として表すことによって,より短い文字列に減少する簡単な無損圧縮法を学習した.
例えば、aabacccについては、2 a 2 ba 3 c(文字が重複せず、一度しか出現せず、1を省略する)と表すことができ、この方法の欠点は、重複文字が少ない場合に圧縮率が低いことである.たとえばabcabcdedeのような文字列は圧縮されません.この欠点を解決するために、ピッチは、文字列を1つ以上の単位に切り取って圧縮し、より短い文字列として表す方法を探します.
例えば、abbcdcababcdcdの場合、文字を1単位に切り取ると全く圧縮されないが、2単位に切り取ると2 ab 2 cdとして表すことができる.異なる方法で8単位でせん断と圧縮を行う場合は、2 abbcdcdを用いて表すことができ、この場合圧縮が最も短い.
別の例はabcabcdedeであり、文字を2単位に切り取って圧縮するとabcabc 2 deであり、3単位に切り取ると2 abcdedeであり、この3単位が最も短い圧縮方法である.3つの単位を切り取り、最後に残った文字列を貼り付けます.
圧縮する文字列sをパラメータとして指定する場合は、上述した方法に従って1つ以上の単位で文字列を切り取り、solution関数を完了して、表す文字列の中で最も短い長さを返します.
せいげんじょうけん
sの長さは1または1000以下である.
sは小文字のみからなる.
I/O例
s result
"aabbaccc" 7
"ababcdcdababcdcd" 9
"abcabcdede" 8
"abcabcabcabcdededededede" 14
"xababcdcdababcdcd" 17
I/O例説明
I/O例#1
文字列を1つの単位で切り取って圧縮する場合に最も短い.
I/O例#2
文字列を8単位で切り取って圧縮する場合が最も短い.
I/O例#3
文字列を3つの単位で切り取って圧縮する場合に最も短い.
I/O例#4
文字列を2つの単位で切断すると、その文字列はabcabcabc 6 deになります.
文字列を3単位に切り取ると、4 abcdededededededeedが生成されます.
文字列を4単位に切り取るとabcabcabc 3 dedeが生成されます.
文字列を6単位で切断すると、2 abcabc 2 dedeとなり、長さは最短14となる.
I/O例#5
文字列は、先頭から指定した長さで切り捨てなければなりません.
したがって、所与の文字列をx/abbcdcd/abbcdcdに切り取ることはできない.
この場合、最も短い長さは17であり、どうしても文字列を切り取っても圧縮されないためである.
def solution(s): # 입력받은 문자열 s
# before
result = length = len(s)
cnt = 0
before = ''
for i in range(1, length // 2 + 1):
arr = [s[j:j+i] for j in range(0, length, i)] # i의 길이단위로 문자열 자르기
# arr = list(map(''.join, zip(*[iter(s)] * i)))
string = '' # i의 길이 단위로 잘라 압축했을 때의 결과값 저장
before = '' # 이전 문자열 저장
cnt = 0 # 동일 문자열 세는 변수 0으로 초기화
for k in arr:
if before == k: # 이전 문자열과 동일한 경우
cnt += 1
else: # 동일하지 않을 경우 경우 3가지로 나뉨
if cnt == 0: # 가장 처음 요소인 경우는 cnt = 0
cnt += 1
pass
elif cnt == 1: # before 문자열이 한번 나타난 경우는 1제외하고 문자열만 append
string += before
else:
string += str(cnt) + before
cnt = 1
before = k
# 요소 남은 경우
if cnt != 1:
string += str(cnt) + before
else:
string += before
result = min(result, len(string)) # 반복할 때마다 짧은 길이 갱신
return result
文字列を一定の長さで切り捨てるs:文字列、length:文字列長、i:トリミングする長さ単位
arr = [s[j:j+i] for j in range(0, length, i)]
arr = list(map(''.join, zip(*[iter(s)] * i)))
Reference
この問題について([プログラマ]文字列の圧縮), 我々は、より多くの情報をここで見つけました https://velog.io/@ayoung0073/algorithm-kakao-문자열압축テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol