99클럽 코테스터디 6기 11일차 TIL (LeetCode 187)

📌문제접근

문제 : LeetCode 187. Repeated DNA Sequences
유형 : 문자열, 비트맵, 해시테이블

1) string에서 반복되는 substring 찾기
2) substring의 길이가 10으로 고정되어있기에 길이가 11이상인 string부터 확인하면 된다
3) substring을 잘라내여 <string, int> 해시맵에 저장하고 동일한 substring이 있는 경우 int값을 +1 한다

📌제출코드

1. substring 이용

class Solution {
    string subStr;
    unordered_map<string, int> strMap;
public:
    vector<string> findRepeatedDnaSequences(string s) {
        vector<string> result;
        int len = s.length();
        if (len < 11) 
            return result;

        for (int i = 0; i <= len-10; i++) {
            subStr = s.substr(i, 10);
            auto key = strMap.find(subStr);
            if (key != strMap.end()) {
               key->second++;
                continue;
            } 
            strMap.insert({subStr, 0});    
        }
        for (auto& k : strMap) {
            if (k.second > 0)
                result.push_back(k.first);
        }
        return result;
    }
};

2. 2비트 인코딩을 이용한 슬라이딩 비트마스크 + 해시맵

class Solution {
    unordered_map<char, int> charToBit = {
        {'A', 0b00}, {'C', 0b01}, {'G', 0b10}, {'T', 0b11}
    };
    unordered_map<int, int> bitMap;
    vector<string> result;
    
public:
    vector<string> findRepeatedDnaSequences(string s) {
        int len = s.length();
        if (len <= 10) return result;
        int bit = 0;

        for (int i = 0; i < 10 ; i++) {
            bit = bit << 2 | charToBit[s[i]];
        }
        bitMap.insert({bit, 0});
        int mask = (1 << 20) - 1;
        for (int i = 1; i < len - 9; i++) {
            bit = (bit << 2 | charToBit[s[i + 9]]) & mask;

            auto b = bitMap.find(bit);
            if (b != bitMap.end()) {
                b->second++;
                if (b->second == 1 ) result.push_back(s.substr(i, 10));
                continue;
            }
            bitMap.insert({bit, 0});
        }
        return result;
    }  
};

📌문제 해결

비트연산이 익숙치 않아서 개념을 한번 정리하고 구현하였다.
2비트 인코딩을 이용한 해시맵 방식이 시간효율성 면에서 훨씬 뛰어났다.

비트 인코딩과 마스킹

DNA는 'A', 'C', 'G', 'T' 4개의 문자로 되어있어 각각을 2비트 이진수로 표현할 수 있다. 이를 위해

unordered_map<char, int> charToBit = {
{'A', 0b00}, {'C', 0b01}, {'G', 0b10}, {'T', 0b11}
}; 

해시맵을 사용해 각 문자를 대응되는 비트값으로 매핑한다.
문제에서는 중복된 10글자 DNA 시퀀스를 찾는 것이 목표이며, 각 글자를 2비트로 표현하면 총 20비트이기에 10글자를 int(32비트)에 담을 수 있다. 이를 비트 연산을 통해 순차적으로 인코딩한다.

bit = (bit << 2) | 다음_비트;

하지만 비트 인코딩을 반복하다 보면 20비트를 초과한 상위 비트가 남게 될 수 있기에 항상 최근 10글자만 유지하기 위해 마스킹을 적용한다.

int mask = (1 << 20) - 1; //하위 20비트가 1인 카스트
bit = (bit << 2 | 다음_비트) & mask;

&mask를 통해 하위 20비트에만 유지하고, 상위비트를 제거하여 bit 변ㅅ는 항상 최근 10글자의 정보만 담게 된다.

📌오늘의 회고

문제를 푸는 것은 어렵지 않았지만 구현 코드의 시간효율이 좋지 않았다. 비트맵을 이용하여 다시 풀 예정이다.

+) 2비트 인코딩을 통한 문제 해결 코드 업로드 완료