[Baekjoon] 1662. 圧縮[G 5]

📚 質問する

https://www.acmicpc.net/problem/1662
最初に簡単に考えた方法はK(Q)を数値に変換し,再帰関数を用いて値を常に解放することである.enumerate()関数を使用して、一番奥の()を検索します.(出会うたびにindexをその時の値に変換)、出会うとその時のindexを同時に保存し、一番奥の(,)indexを格納するために返します.
indexが保存されている場合は、K(Q)を使用してQ~Qの長さをKに変更し、文字列に入れる.

📒 プライマリコード

def un_zip(string):
    start_i = 0
    last_i = 0
    for i, v in enumerate(string):
        if v == '(':
            start_i = i
        elif v == ')':
            last_i = i
            break
    if start_i == 0:
        return len(string)
    un_zip_str = int(string[start_i-1])*string[start_i+1:last_i]
    new_str = string[:start_i-1] + un_zip_str + string[last_i+1:]
    return un_zip(new_str)

print(un_zip(input()))

しかし、このようにすると、文字列の長さが長すぎてメモリが過剰になるのが問題です.

🔍 主な結果

解決のために4時間符号化...最初は、input()ではなくsys.stdin.readline()を使用すると、タイムアウトやメモリオーバーフローの問題を解決できますが、メモリオーバーフローも発生します.😢
最終的には、卵殻を解いてオリジナルを作り、最後に個数を見つけるのではなく、(Q)の中の文字列の個数まで数え、Kを乗じて「K*Qの長さ」で文字列に入れて繰り返します.
()内に<>がある場合は、数値そのものが長さになるので、<>ではない数値の個数にその値を加算して繰り返し続けます.
次に、このアルゴリズムを適用するコードを示します.

📒 最終コード

import sys

def un_zip(string):
    start_i = 0
    last_i = 0
    un_zip_str_len = 0
    cnt = 0
    open_i = 0
    close_i = 0
    for i, v in enumerate(string):  # ()를 찾아준다.
        if v == '(':    # index 순서대로 찾으며 (가 새로 들어올 때마다 저장
            start_i = i
        elif v == ')':  # )를 만나면 그 때를 last_i에 담고 break
            last_i = i
            break
    if start_i == 0:    # ()가 없을 때 조건문을 읽는다. 마지막 답 구할 때 사용
        if '<' in string:      # <, >를 찾아 안에 값은 숫자로 더해준다.
            for i,v in enumerate(string):
                if v == '<':
                    open_i = i
                    un_zip_str_len += cnt
                    cnt = 0
                elif v == '>':
                    close_i = i
                    un_zip_str_len += int(string[open_i+1:close_i])
                    cnt = 0
                else : cnt += 1 # < > 이외에 있는 값들은 갯수로 센다.
            un_zip_str_len += cnt
        else: 
            un_zip_str_len = len(string)
        return un_zip_str_len
    
    if '<' in string[start_i+1:last_i]: # ()가 있을 땐 여기로 들어온다.
        un_zip_str = string[start_i+1:last_i]
        for i, v in enumerate(un_zip_str):
            if v == '<':
                open_i = i
                un_zip_str_len += cnt
                cnt = 0
            elif v == '>':
                close_i = i
                un_zip_str_len += int(un_zip_str[open_i+1:close_i])
                cnt = 0
            else : cnt += 1
        un_zip_str_len += cnt
        un_zip_str_len *= int(string[start_i-1])
    else : un_zip_str_len = int(string[start_i-1])*(last_i - start_i-1)
    
    new_str = string[:start_i-1] + '<'+ str(un_zip_str_len) + '>' + string[last_i+1:]
    return un_zip(new_str)

print(un_zip(sys.stdin.readline().strip()))

🔍 最終結果

これにより、メモリ過剰の問題が解決します.
彼は6時間ほどハミングして、コードの長さと速度が比例していないことがやっと分かった.
50行ほど出てきましたが、よりクリーンにコードを生成するためには、アルゴリズム学習+解法量を増やすべき!
注釈処理習慣やコードが長くなると,中間Gitに情報をアップロードして修正する習慣を身につけるべきである.