[C++] HackerRank : 문자열 알고리즘

 

 

코딩테스트 대비를 위해

해커랭크에서 문자열 관련 알고리즘

연습하기..!

 

---

 

1. String Construction (Easy)

 

 

📌 문제 요약

문자열을 구성할 때, 처음 등장하는 문자는 1달러,
이미 등장한 문자는 복사하며 비용은 0달러 이다.

총 비용을 계산 !

 

구현 코드

int stringConstruction(string s) {
    int freq[26] = {}, cnt = 0;
    
    for(char c : s) {
        if(freq[(c-'a')]==0) {
            cnt++;
            freq[(c-'a')]=1;
        }
    }

    return cnt;
}

 

💡 알고리즘 요약

문자열의 서로 다른 문자 개수가 곧 정답

 

구현 팁

unordered_set<char> or bool seen[26] 이용

 

 

---

 

 

2. Two Characters (Easy)

 

📌 문제 요약

문자열에서 두 문자만 남기고 지워서 나오는 가장 긴 문자열을 만들기

 

구현 코드 (이중 for문 + 필터링)

// 개선 버전
int alternate(string s) {
    int result = 0;
    int chk[26] = {};
    vector<char> freq;

    // 중복 없는 문자 모음 생성
    for (char ch : s) {
        if (!chk[ch - 'a']) {
            chk[ch - 'a'] = 1;
            freq.push_back(ch);
        }
    }

    for (int i = 0; i < freq.size(); ++i) {
        for (int j = i + 1; j < freq.size(); ++j) {
            char a = freq[i], b = freq[j];
            string filtered = "";

            for (char ch : s) {
                if (ch == a || ch == b) {
                    filtered += ch;
                }
            }

            if (filtered.length() < 2) continue;

            bool isValid = true;
            for (int k = 1; k < filtered.size(); ++k) {
                if (filtered[k] == filtered[k - 1]) {
                    isValid = false;
                    break;
                }
            }

            if (isValid) {
                result = max(result, (int)filtered.size());
            }
        }
    }

    return result;
}

 

구현 코드 (next_permutation + 직접 삭제)

int TwoCharaters(string s){
    int result = 0;
    
    vector<char> freq;
    int chk[26] = {};
    
    for(int i=0; i<s.length(); i++) {
        if(chk[(s[i]-'a')] == 0){
            freq.push_back(s[i]);
            chk[(s[i]-'a')]=1;
        }
    }
        
    int len = freq.size();
    vector<bool> temp(len);
    fill(temp.end()-(len-2), temp.end(), true);
    
    do{
        string new_S = s;
        for(int i=0; i<s.length(); i++){
            if(temp[i]){
                char c = freq[i];
                
                while(new_S.find(c) != std::string::npos){
                    new_S.erase(find(new_S.begin(), new_S.end(), c));
                }
            }
        }
        
        if(new_S.length() < 2) continue;
        
        char prevChar = ' ';
        for(int i=0; i<new_S.length(); i++){
            if(prevChar != new_S[i]){
                prevChar = new_S[i];
                if(i == new_S.length()-1) 
                    result = (result < new_S.length()) ? new_S.length() : result;
            }
            else if(prevChar == new_S[i]) break;
        }
        
    }while(next_permutation(temp.begin(), temp.end()));
    
    return result;
}

 

 

💡 알고리즘 요약

알파벳 조합(26C2 = 325쌍)에 대해
→ 해당 두 문자만 필터링
→ 인접 문자가 반복되면 무효
→ 유효한 것 중 최대 길이 계산

 

구현 팁

필자는 next_permutation를 사용하여 풀었으나

이중 for문 + 필터링이 깔끔

필터된 문자열의 2글자 이하라면 예외처리 !

 

---

 

3. Making Anagrams (Normal)

 

📌 문제 요약

두 문자열을 아나그램으로 만들기 위해 삭제해야 할 최소 문자 수

*Anagram은 문자를 재배치하여 다른 단어로 바꾸는것

 

구현 코드

int makingAnagrams(string s1, string s2) {
    int result = 0;
    int freq[26] = {};
    
    for(char c : s1) freq[(c-'a')]++;
    for(char c : s2) freq[(c-'a')]--;
    for(int i=0; i<26; i++) if(freq[i] != 0 ) result += abs(freq[i]);
    
    return result;
}

 

💡 알고리즘 요약

두 문자열 각각에 대해 문자 빈도수 계산

각 알파벳마다 차이를 더함

문자 빈도수의 차이는 곧 우리가 삭제해야 할 문자의 수

 

구현 팁

int freq1[26], freq2[26] 활용 → 차이 누적

 

---

 

4. Special String Again (Normal)

 

📌 문제 요약

주어진 문자열에서 다음 2가지 조건의 부분 문자열 개수 구하기

1. 모든 문자가 같은 경우

2. 가운데 하나만 다른 대칭 문자열 = 회문, 팰린드롬 ("aabaa" 등)

 

long substrCount(int n, string s) {
    long result = 0;
    
    // 연속된 같은 문자로 이루어진 문자열
    for(int i=0; i<n;){
        int repeat = 1;
        while(i+repeat < n && s[i]==s[(i+repeat)]) repeat++;
        
        result += repeat*(repeat+1)/2;
        i += repeat;
    }
    
    // 팰린드롬
    for(int i=1; i<n-1; i++){
        int offset = 1;
        while(
            (i+offset < n) &&
            (i-offset >= 0) &&
            (s[i-offset] == s[i-1]) &&
            (s[i+offset] == s[i+1]) &&
            (s[i-1] != s[i]) &&
            (s[i-1] == s[i+1])
        ){
            offset++;
            result++;
        }
    }

	return result;
}

 

💡 알고리즘 요약

조건 1. 같은 문자 연속 구간 길이 n → n(n+1)/2 개 (=등차수열의 합)

조건 2: 각 인덱스를 중심으로 좌우 확장하면서
"aabaa" 구조가 되는지 체크 (s[i] != s[i-1] 등)

 

구현 팁

s[i-1] == s[i+1] 조건을 명시적으로 넣으면 정확도 향상

offset 이용한 양쪽 확장 구조 정확히 구현

 

---

 

5. Sherlock and Anagrams (Normal)

 

📌 문제 요약

부분 문자열 중 애너그램 쌍의 개수를 구하는 문제

* 애너그램 = 문자 구성(빈도)이 같은 문자열

 

int sherlockAndAnagrams(string s) {
    unordered_map<string, int> m;
    int result = 0;

    for(int i=0; i<s.length(); i++){
        int freq[26] = {};
        
        for(int j=i; j<s.length(); j++){
            freq[s[j]-'a']++;

            string key = "";
            for(int k=0; k<26; k++) key += to_string(freq[k]);
            m[key]++;
        }
    }

    for(auto value : m){
        int count = value.second;
        if(count > 1){
            result += (count * (count-1)) / 2;
        }
    }

    return result;
}

 

💡 알고리즘 요약

모든 부분 문자열을 탐색하면서 알파벳 빈도 배열을 구해 unordered_map<string, int>에 카운트

같은 빈도 배열이 n개면, 쌍의 수는 nC2 = n(n-1)/2

 

구현 팁

vector<int> → string으로 변환해서 key로 사용 (hash map용)

조합 수 계산 시 오버플로우 주의

 

---

 

끝!