Bear and Steady Gene

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

✅ Problem Summary

입력된 곰의 염기서열을 최소한으로 수정하여 안정적인 형태(염기를 구성하는 A,C,G,T 가 n = 문자열길이 일 때, $\frac{n}{4}$ 개로 존재하는 상태)로 만드는 문제

---

📑 My Answer

• 모든 테스트 케이스 통과

def steadyGene(gene):
    gene_dic = {'A':0, 'C':0, 'G': 0, 'T':0}
    for c in gene: gene_dic[c]+=1
    gene_len = len(gene)
    min_len, n = gene_len, gene_len/4
    left, right = 0,0
    while left < gene_len and right < gene_len:
        if False in [x <= n for x in gene_dic.values()]:
            gene_dic[gene[right]] -= 1
            right += 1
        else:
            min_len = min(min_len, right-left)
            gene_dic[gene[left]] += 1
            left += 1
    return min_len

📌 코드 구현 설명

• 입력된 염기서열을 순회하여 각 염기의 갯수를 센 후, 0 부터 시작하는 두 개의 포인터(left, right)를 사용하여 염기서열 전체를 탐색한다.
• 먼저right를 1 씩 증가시키면서 각 염기의 갯수가 $\frac{n}{4}$개 이하가 될 때 까지 (해당 염기의 전체 개수 - 1) 을 수행한다. → 갯수가 넘친 염기의 자리를 다른 염기에게 줄 수 있도록 따로 빼놓는 작업
• 모든 염기가 $\frac{n}{4}$개 이하가 되었다면, left를 1 씩 증가시키면서 모든 염기가 $\frac{n}{4}$개가 될 때 까지 (해당 염기의 전체 개수 + 1) 을 수행한다. → 따로 빼놓았던 자리를 각 염기에 할당하여 염기서열을 안정화 시키는 작업
• 이때, left와 right의 사이의 길이를 계산하고 매 단계마다 최소 길이로 갱신

---

💼 Takeaway

• 이러한 형태의 코드 설계(두 개의 변수를 사용하여 데이터 위치를 저장하여 처리하는 것)를 투포인터 (Two Pointers) 기법이라고 부른다.

• 투포인터 기법의 하위 개념으로 슬라이딩 윈도우(Sliding Window) 기법이 있으며, 포인터 간의 거리가 가변적인 투포인터와는 다르게 거리(윈도우 크기)가 고정되어 사용된다.

---