[HR] string : Bear and Steady Gene ★

문제
https://www.hackerrank.com/challenges/bear-and-steady-gene/problem?isFullScreen=true

문제 요약

• 선택한 substring의 문자들을 마음대로 바꿀 수 있다고 할 때, 문자열에서 A, C, T, G의 출현 빈도를 동일하게 만드는 가장 짧은 substring의 길이를 구하시오.

아이디어

• 문자열의 길이를 4로 나누면 각 문자(A, C, T, G)의 목표 빈도가 계산된다.
• 각 문자가 몇번 출현했는지 계산하기 위해 Counter를 사용한다.
• Counter에 문자열을 넣으면서 4를 빼면 교체해야할 각 문자의 수가 계산된다.
• 이 문자의 수를 다 더하면 교체해야할 문자열의 최소 길이가 계산된다.
• 모든 substring을 보면서 교체해야할 각 문자의 수가 포함된 substring의 길이를 구한다.
• 가장 짧은게 답이다.

1차 고뇌

• 모든 substring을 돌기 위해서 sliding window를 생각했다.
• 최소 길이부터 문자열 끝까지 스캔하고 길이를 하나 늘려서 다시 스캔하는 방식이다.
• 중첩 for loop 나 (start, end) 인덱스를 활용한 while문을 사용해서 substring을 선택 할 수 있다.
• 모든 loop에서 선택한 substring의 Counter를 계산해서 미리 계산해둔 목표 Counter와 비교하면 된다.

코드(유효성 실패)

• 두가지 버전 모두 유효성 테스트를 통과하지 못한다.
• 첫번째 버전은 정답 substring의 길이가 길고 뒤쪽에 위치했을 때 그 전에 스캔할 데이터가 너무 많다.
• 두번째 버전은 문자가 하나씩 추가/제거 될때마다 모든 loop에 대해 Counter를 만들어줘야 하니, 비효율적이다.

from collections import Counter
def steadyGene(gene):
    # Write your code here
    gene_len = len(gene)
    expected_len = gene_len//4
    lst = ["G", "A", "C", "T"]
    occur = Counter()
    found = Counter()
    target = set()
    

    for char in lst:
        cnt = gene.count(char) - expected_len
        if cnt > 0 :
            occur[char] = cnt
            found[char] = 0
            target.add(char)
    least = sum(occur.values())
    if least == 0:
        return 0
    """
    ver1
    """
     for i in range(least, gene_len):
         for j in range(0, gene_len-i+1):
             if (i+j)-(j) < least:
                 break
             elif gene[j] not in occur:
                 continue
            
             if not (occur - Counter(gene[j:i+j])):
                 return (i+j)-(j)
    """
    ver2
    """
     start = 0
     end = least - 1
    
     while end != gene_len:
        
         if end == gene_len and start+least >= end:
             break
         cur = Counter(gene[start:end])
         check = occur - cur 
         check2 = gene[start] in occur
         # print("! ", start, end, cur, check, check2)
         if not check:
             all_lst.append(len(gene[start:end]))
             start += 1
         else:
             end += 1
             if not check2:
                 start+=1
                
     return min(all_lst)

코드(성공)

• Two Pointers 기법을 활용해 조건을 만족하는 최소 substring의 길이를 저장해두고, 각 loop에서 추가/제거된 문자에 대해서 길이를 더해주거나 빼는 로직이다.

from collections import Counter
def steadyGene(gene):
    # Write your code here
    gene_len = len(gene)
    expected_len = gene_len//4
    lst = ["G", "A", "C", "T"]
    occur = Counter()
    found = Counter()
    target = set()
    

    for char in lst:
        cnt = gene.count(char) - expected_len
        if cnt > 0 :
            occur[char] = cnt
            found[char] = 0
            target.add(char)
    least = sum(occur.values())
    if least == 0:
        return 0
        
    """
    ver3
    """
    
    tail = 0
    head = 0
    print(found)
    min_len = gene_len
    while head != gene_len:
        found[gene[head]] += 1
        flag = True
        print(found)
        for t_char in target:
            if found[t_char] < occur[t_char]: # need to find(include) more characters in 'found'
                flag = False
        
        if flag == True:
            # this is a valid candidate
            min_len = min(min_len, head-tail+1)
             
            # try to shorten it by cutting the left
            while found[gene[tail]] > occur[gene[tail]]:
                found[gene[tail]] -= 1
                tail += 1
                min_len = min(min_len, head-tail+1)
        head += 1
    
    return min_len