Q1. 文字列圧縮

1.質問のタイプ

Programmersリンク共有
https://programmers.co.kr/learn/courses/30/lessons/60057

1-1. I/O例

ソースコード

INF = int(1e9)

def solution(s):
    answer = INF
    
    if len(s) == 1: # 길이가 1일 때, return 1
        return 1
    
    for cutPoint in range(1,len(s)//2+1):
        ans = ""
        count = 1
        tmpStr = s[:cutPoint]
        
        for idx in range(cutPoint,len(s),cutPoint):
            if tmpStr == s[idx:idx+cutPoint]:
                count += 1
            else:
                if count == 1:
                    count = ""
                ans += str(count) + tmpStr
                tmpStr = s[idx:idx+cutPoint]
                count = 1
        
        if count == 1:
            count = ""
        
        ans += str(count) + tmpStr
        answer = min(answer,len(ans))
    
    return answer

3.問題を解く

この問題は文字列を処理するアルゴリズムであり,文字列を自分の望む状態に切り取ることができるかどうかが鍵となる.

Python文字列の切り取り方法
Arr[A:B]>範囲:AからB-1(インデックスベース)
Arr[A:]>範囲:A~終了(インデックスベース)
Arr[:B]>範囲:初期インデックスからB-1インデックス)

上記の方法を理解すれば、少しでも簡単に近づけます.

3-1. カットポイントの設定

まず、カットされた文字列をいくつか比較するためにcutPointを設定します.

for cutPoint in range(1,len(s)//2+1):
	count = 1
	ans = ""
	tmpStr = s[:cutPoint]

tmpStor:初期文字列(=s)で1文字のみ切り取る文字列

count:同じ文字列数(初期値:1)

ans:現在の圧縮文字列を格納する変数

for文を初期文字列(=s)の長さの半分を超えないように設定
WHY? 半分を超えると圧縮はもう意味がないからだ.

3-2. 比較文法

次に、for文を実装して、3-1から切り取られた文字列(=tmpstr)と比較します.

for idx in range(cutPoint, len(s), cutPoint):
	if tmpStr == s[idx:idx+cutPoint]:
		count += 1
	else:
		if count == 1:
			count = ""
		ans += str(count) + tmpStr
		tmpStr = s[idx:idx+cutPoint]
		count = 1

for文の値をcutPoint値に増やすことで、同じ長さの文字列を比較できます.
標準文字列(=tmpStr)が次の文字列(=s[idx:idx+cutPoint])と同じ場合count+=1

そうでなければ、
1.同じ値が1つしかない場合は、その値を省略します.
2.ansに現在までの同じ数(=count)+文字列(=tmpstr)を保存
3.tmpStorを新しい文字列として再定義しcount=1

に初期化する

3-3. 最小の長さを求める

3-2が完了したら、for文の値が最小長であるかどうかを比較する必要があります.

if count == 1:
	count = ""
ans += str(count) + tmpStr
answer = min(answer, len(ans)

3-2のfor文を脱出した後、同じ文法を再使用する必要がある理由は?

最後の文字列

を処理できません.
上記の手順に従って、既存の答えと現在見つかっている圧縮文字列(=ans)の長さを使用して、より小さな値を置き換えます.
この手順を繰り返すと、答えに最小の圧縮文字列長が格納されます.

4.終了

今日は文字列を処理するアルゴリズムの問題を解いた.Pythonは文字列を扱いやすいので便利ですが、アルゴリズムを考え出すのに時間がかかったようです.
解ければ解けるほど解けるという考え方よりも、なかなか難しいです.ㅠまだ長い道があるでしょう...
もっと忙しく前に进め!
完全なソースGitリンク
https://github.com/cho876/Algorithm/blob/master/Problem/Kakao/2020_kakao_blind_recruitment_q1.py