Bear and Steady Gene

사이트: HackerRank
난이도: 미디움
분류: String

문제

주어진 곰의 유전자 문자열에 존재하는 각각 문자 들의 개수가 n/4이 될 수 있도록 하는 최소 변경 횟수를 반환하라. 유전자 문자열에 존재할 수 있는 문자들은 A, C, T, G 이다.

1. 나의 풀이

문제가 이해되지 않아 바로 풀이방법을 찾아보았다.

2. 다른사람의 풀이

투 포인터 알고리즘을 사용하여 해결하는 문제이다. 주어진 문자열 gene을 순회하면서 각 문자들이 등장하는 횟수를 기록하고, 각 문자들의 등장횟수가 n/4가 될 수 있도록 두 개의 포인터를 조작한다.

left 변수는 모든 문자의 개수가 n/4개 이하일 경우 1씩 증가 된다.
right 변수는 하나라도 문자의 개수가 n/4개 이상일 경우 1씩 증가 된다.

문자열 GAAATAAA가 주어지고 left 변수가 ", right 변수가 '를 나타낸다고 할 때 진행상황은 아래와 같다.

"'GAAATAAA

// A의 개수가 8/4, 즉 2를 넘기므로 right를 1 증가시킨다.
"G'AAATAAA

// 아직도 2를 넘기므로 right를 증가시킨다. A가 2개 남을 때까지 증가시킨다.
"GAAATA'AA

// 모든 문자의 개수가 2를 초과하지 않으므로, left를 증가시킨다. 이 때 최소 변경값이 계산된다.(minLen=6)
G"AAATA'AA

// 마찬가지로 left를 증가시킨다.(minLen=5)
GA"AATA'AA

// A가 2를 초과했으므로 right를 증기시킨다.
GA"AATAA'A

// 모든 문자의 개수가 2를 초과하지 않으므로, left를 증가시킨다.(minLen=5)
GAA"ATAA'A

// A가 2를 초과했으므로 right를 증가시킨다.
GAA"ATAAA'

// 모든 문자의 개수가 2를 초과하지 않으므로, left를 증가시킨다.(minLen=5)
GAAA"TAAA'

// A가 2를 초과했으므로 right를 증가시킨다.
GAA"ATAAA '
// right가 문자열의 길이와 같아졌으므로 루프를 종료한다.
// minLen=5 가 반환된다.

function steadyGene(gene) {
    // Write your code here
    const geneDic = { 'A':0, 'C':0, 'G': 0, 'T':0 };
    Array.from(gene).forEach(c => geneDic[c]++);
    
    const n = gene.length / 4;
    let left = 0, 
        right = 0,
        minLen = Infinity;

    while(left < gene.length && right < gene.length) {
        if (Object.values(geneDic).some(v => v > n)) {
            geneDic[gene[right]]--;
            right++;
        } else {
            minLen = Math.min(minLen, right - left);
            geneDic[gene[left]]++;
            left++;
        }
    }

    return minLen;
}