日付4のエクスポート|ラッキー・ストリング、文字列の再配置、圧縮文字列

33310 ワード

📍 これがコードテスト(羅東彬)-第3部アルゴリズムタイプ固有のエクスポート問題を解決し記録した.

1.ラッキーストレート

  • 現在のキャラクターの点数がNの場合、数字の桁数によって点数Nを半分に分けることができ、左側の各桁数の和と右側の各桁数の和を加算した値が同じ場合に「ラッキートレイ」技術を使用します.
  • 1行目の分数Nは整数である.(10<= N<= 99,999,999)
  • セグメントNは常に偶数形式で与えられる.
  • 出力条件)ラッキーバーが利用可能であれば「LUCKY」、無効であれば「READY」を出力する

    1.1私の答え

  • 文字列に入力し、リストに変換して商品を生成する
  • 
    n = list(input())
    front = n[:len(n)//2]
    back = n[len(n)//2:]
    
    front = list(map(int, front))
    back = list(map(int, back))
    
    if sum(front) == sum(back):
      print("LUCKY")
    else:
      print("READY")
    

    1.2本の答え

  • 左の和を加え、右の和を除いて、最終的にゼロであることを確認します.
  • # 12시 51분
    n = input()
    length = len(n) # 점수값의 총 자릿수
    summary = 0
    
    # 왼쪽 부분의 자릿수 합 더하기
    for i in range(length//2):
      summary += int(n[i])
    
    # 오른쪽 부분의 자릿수 합 빼기
    for i in range(length//2, length):
      summary -= int(n[i])
    
    # 왼쪽 부분과 오른쪽 부분의 자릿수 합이 동일한지 검사
    if summary == 0:
      print('LUCKY')
    else:
      print('READY')
    

    2.文字列の並べ替え

  • 大文字と数字(0~9)のみからなる文字列を入力します.文字列の長さは1または10000未満です.
  • この場合、すべてのアルファベットを昇順に並べて出力
  • その後すべての数字の値を加算して出力
  • 例)入力)K 1 KA 5 CB 7->出力)ABCKK 13

    2.1私の答え

    s = input()
    
    char_list = ['0','1','2','3','4','5','6','7','8','9']
    char = []
    num = 0
    for w in s:
      if w in char_list:
        num += int(w)
      else:
        char.append(w)
    char.sort()
    result = ''.join(char) + str(num)
    print(result)
    

    2.2本の答え

  • is.Alpha():アルファベットかどうかを確認します.
  • data = input() 
    result = []
    value = 0
    
    # 문자를 하나씩 확인하며
    for x in data:
      # 알파벳인 경우 결과 리스트에 삽입
      if x.isalpha():
        result.append(x)
      # 숫자는 따로 더하기
      else:
        value += int(x)
    
    # 알파벳을 오름차순으로 정렬
    result.sort() 
    
    # 숫자가 하나라도 존재하는 경우 가장 뒤에 삽입
    if value != 0:
      result.append(str(value))
    
    print(''.join(result))
    

    3.文字列圧縮


    データ処理の専門家になりたい「音声器」は、文字列を圧縮する方法を学んでいる.最近,文字列に連続的に現れる同じ値を文字数と繰返し値として表すことによって,より短い文字列に減少する簡単な無損圧縮法を学習した.
    例えば、「aabbacc」については、「2 a 2 ba 3 c」と表すことができ(文字が1回繰り返されていない場合は1を省略する)、このような方式の欠点は、重複文字が少ない場合に圧縮率が低いことである.たとえば、文字列「abcabcdede」は完全に圧縮されません.この欠点を解決するために、「ピッチ」は、文字列を1つ以上の単位に切り取ることで圧縮し、より短い文字列として表す方法を探します.
    たとえば、「abbcddababccdcdd」は、文字を1単位に切り取ると全く圧縮されず、2単位に切り取ると「2 ab 2 cd 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)
    sresult"aabbaccc"7"ababcdcdababcdcd"9"abcabcdede"8"abcabcabcabcdededededede"14"xababcdcdababcdcd"17

    3.1私の答え


    最初の答え
  • 圧縮可能か検証check関数エラー
  • xababab->x3ab前から圧縮が不可能だと思うのは無理
  • そうではないxababab->x3ab単位=2であれば、先にxが1つしか残っていない(長さ=1).これでは、文字列を単位2に分割した結果ではありません.
  • aaaaaaaaaabb->10a2b重複回数が1桁を超える場合も考慮
  • def solution(s):
        length = len(s)
    
        # 압축 가능한지 확인하는 함수
        def check(): 
            answer = False
            for i in range(1,length//2+1): 
                if s[:i] == s[i:2*i]:
                    answer = True
                    break
            if
            return answer
        
        # 압축 안되는 경우
        if check() == False:
            return length
        
        # search : 출발 인덱스 i, 단위 n 으로 문자열 s를 압축하여 길이를 리턴하는 함수
        def search(i, n, s) : 
            pre_pattern = s[i:i+n] # 반복 패턴
            pre_count = 1 # 반복 횟수
            count_list = [] # pre_count로 이루어진 리스트
            while (i+2*n) <= length:
                if pre_pattern == s[i+n:i+2*n]: # 그다음 n개도 반복될 때
                    pre_count += 1 #반복되는 카운트 늘림. 
                else: # 반복 끝
                    if pre_count > 1: # 2번 이상 반복된 경우에만 압축
                        count_list.append(pre_count)
                    pre_pattern = s[i+n:i+2*n] # 그 다음 확인할 패턴
                    pre_count = 1 # 카운트도 초기값으로
                i += n
            # 마지막 카운트가 2 이상이라면 count_list에 append하고 종료
            if pre_count > 1:
                count_list.append(pre_count)
            
            # l1 : i부터 단위 n으로 압축한 부분의 길이
            count_length = [len(str(x)) for x in count_list] # 반복되는 숫자의 자릿수
            l1 = len(count_list)*n + sum(count_length)
            # l2 :압축되지 않은 부분의 길이 n*
            l2 = length-sum([x*n for x in count_list])
            return l1+l2
        
        # i와 n을 변화해가면서 압축
        record = []
        min_length = 1000
        for n in range(1,length//2+1):
            for i in range(length-2*n+1): # 반복을 확인하려면 최소한 2*n전에 인덱스가 시작
                min_length = min(min_length,search(i, n, s))
        
        
        return min_length
    二つ目の答え
  • 出発インデックスiは1個ずつ増加するのではなく、1個n単位で増加する.このようにしてこそ、すべてのsを同じ単位nに分けることができる.テストケースは次のとおりです.
  • xababab->非圧縮
  • xxababab -> xx3ab , result = 5
  • sの長さが1であれば非圧縮処理を別途行う
  • def solution(s):
        length = len(s)
    
        # search : 출발 인덱스 i, 단위 n 으로 문자열 s를 압축하여 길이를 리턴하는 함수
        def search(i, n, s) : 
            pre_pattern = s[i:i+n] # 반복 패턴
            pre_count = 1 # 반복 횟수
            count_list = [] # pre_count로 이루어진 리스트
            while (i+2*n) <= length:
                if pre_pattern == s[i+n:i+2*n]: # 그다음 n개도 반복될 때
                    pre_count += 1 #반복되는 카운트 늘림. 
                else: # 반복 끝
                    if pre_count > 1: # 2번 이상 반복된 경우에만 압축
                        count_list.append(pre_count)
                    pre_pattern = s[i+n:i+2*n] # 그 다음 확인할 패턴
                    pre_count = 1 # 카운트도 초기값으로
                i += n
            # 마지막 카운트가 2 이상이라면 count_list에 append하고 종료
            if pre_count > 1:
                count_list.append(pre_count)
            
            # l1 : i부터 단위 n으로 압축한 부분의 길이
            count_length = [len(str(x)) for x in count_list] # 반복되는 숫자의 자릿수
            l1 = len(count_list)*n + sum(count_length)
            # l2 :압축되지 않은 부분의 길이 n*
            l2 = length-sum([x*n for x in count_list])
            return l1+l2
        
        # 길이 1이면 압축 불가
        if length == 1:
            return 1
        
        # i와 n을 변화해가면서 압축
        record = []
        min_length = 1000
        for n in range(1,length//2+1):
            for i in range(0,length,n): # 반복을 확인하려면 최소한 2*n전에 인덱스가 시작
                min_length = min(min_length,search(i, n, s))
        
        
        return min_length

    3.2本の答え

  • おおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおお
  • 入力文字列長が1000以下であるため、できるだけ多くの完全検索が可能である.
  • 私の答えよりずっと早い.(そのためかどうかは不明)繰り返し回数をリストにずっと保存して、もう1本の圧縮されていない長さを求めました
  • 圧縮後の文字列をリアルタイムで求め、len(圧縮)で圧縮後の文字列長を一度に求める.
  • def solution(s):
      answer = len(s)
      # 1개 단위(step)부터 압축 단위를 늘려가며 확인
      for step in range(1, len(s)//2+1):
        compressed = ''
        prev = s[0:step] # 앞아서부터 step만큼의 문자열 추출
        count = 1
        # 단위(step) 크기만큼 증가시키며 이전 문자열과 비교
        for j in range(step, len(s), step): # answer이 아니라 len(s)를 씀 주의
          # 이전 상태와 동일하다면 압축 횟수(count)가 증가
          if prev == s[j:j+step]:
            count += 1
          else:
            compressed += str(count) + prev if count >= 2 else prev
            prev = s[j:j+step] # 다시 상태 초기화
            count = 1
        # 남아있는 문자열에 대해서 처리
        compressed += str(count) + prev if count >= 2 else prev
        answer = min(answer, len(compressed))
      return answer
        
    
    +他のプログラマが他のユーザーを説明
  • 私は「単位nは1からlen(s)/2+1まで…だからforゲートへ…」私はそう思います.最初からtext、tok lenに関数を書いていましたが、段階的に解くことができましたね