[C++] HackerRank : 해시/맵 알고리즘

 

코딩테스트 대비를 위해

해커랭크에서 해시테이블 관련 알고리즘

연습하기..!

 

---

 

1.Ransom Note (Easy)

 

📌 문제 요약

두 문자열 리스트(megazine, note)에서 단어 빈도 비교

magazine의 단어들로 note를 만들 수 있는지 확인

 

구현 코드

void checkMagazine(vector<string> magazine, vector<string> note) {
    unordered_map<string, int> um;
    
    for(string s : magazine) um[s]++;

    for(string s : note){
        if(um[s]) um[s]--;
        else {
            cout << "No\n";
            return ;
        }
    }
    
    cout << "Yes\n";
}

 

 

💡 알고리즘 요약

unordered_map<string, int> 으로 magazine의 단어 빈도 세기

note의 각 단어가 map에 존재하고, 개수가 충분한지 체크

하나라도 부족하면 "No", 전부 만족하면 "Yes"

 

구현 팁

if (map[word] == 0) 조건으로 빠르게 차단 가능

note 단어를 순회하면서 감소시키는 방식으로 깔끔하게 처리

 

---

 

2. Ice Cream Parlor (Easy)

 

📌 문제 요약

합이 주어진 money가 되는 두 숫자의 인덱스를 찾는 Two Sum 유형

 

구현 코드

void whatFlavors(vector<int> cost, int money) {
    unordered_map<int, int> um;  // 가격 → 인덱스

    for (int i = 0; i < cost.size(); i++) {
        int needed = money - cost[i];
        if (um.count(needed)) {
            // 인덱스는 1-based
            int a = um[needed] + 1;
            int b = i + 1;
            cout << min(a, b) << " " << max(a, b) << "\n";
            return;
        }
        um[cost[i]] = i;
    }
}

 

💡 알고리즘 요약

현재 숫자를 x라고 할 때, (money - x)가 이전에 등장했는지 map으로 체크

발견되면 현재 인덱스와 함께 출력

 

구현 팁

unordered_map<int, int>에 가격(key) → 인덱스(value) 저장

반드시 um.count(차이값) 먼저 확인 후 출력

정답은 하나만 보장되므로 처음 발견되면 return

 

---

 

3. Count Triplets (Normal)

 

📌 문제 요약

등비수열 (a, ar, ar²) 형식의 triplet 개수를 구하는 문제

i < j < k 순서 조건 포함

 

구현 코드

long countTriplets(vector<long> arr, long r) {
    long result = 0;
    if(arr.size()<3) return result;
    
    unordered_map<long, long> left, right;
    
    for(long num : arr) right[num]++;
    
    for(long mid : arr){
        right[mid]--;
        if(mid%r == 0){
            int a = mid / r;
            int b = mid * r;
            
            result += (left[a] * right[b]);
        }
        left[mid]++;
    }
    
    return result;
}

 

💡 알고리즘 요약

right : 전체 배열의 값 빈도 수 (초기화)

순회하면서 현재 값을 중간값으로 가정

왼쪽에는 arr[i]/r, 오른쪽에는 arr[i]*r가 있는지 보고 → 조합수 계산

각 값은 사용 후 right → left로 옮김

 

🔧 구현 팁

if (mid % r == 0) 조건으로 등비 수열 성립 여부 사전 필터링

left, right 맵 동기화 시 주의 ! 항상 한 번씩만 업데이트

결과값은 left[a] * right[c] 누적으로 관리

 

---

 

4. Frequency Queries (Normal)

 

 

📌 핵심 개념

1 x : 삽입, 2 x : 삭제, 3 y : 빈도가 y인 숫자가 존재하는가?

빈도의 빈도를 실시간으로 관리해야 O(1)로 처리 가능

 

구현 코드

vector<int> freqQuery(vector<vector<int>> queries) {
    vector<int> result;
    unordered_map<int, int> um;
    unordered_map<int, int> um_cnt;
        
    for(vector<int> query : queries){
        int cmd = query[0], num = query[1];
        
        if(cmd == 1) {
            int upCnt = um[num];
            um_cnt[upCnt]--;
            um_cnt[upCnt+1]++;
            um[num]++;
        }
        else if(cmd == 2){
            if(um[num]>0) {
                int upCnt = um[num];
                um_cnt[upCnt]--;
                um_cnt[upCnt-1]++;
                um[num]--;
            }
        }
        else if(cmd == 3){
            if(um_cnt[num]>0) result.push_back(1);
            else result.push_back(0);
        }
    }
    
    return result;
}

 

💡 알고리즘 요약

freq[x] : 숫자 x의 등장 횟수

freqCount[f] : 등장 횟수가 f인 숫자 개수

삽입/삭제 시 두 맵 동기화

쿼리 3은 freqCount[y] > 0이면 1, 아니면 0

 

구현 팁

항상 freqCount[old]--, freqCount[new]++ 패턴 사용

삭제할 때 freq[x] > 0 여부 반드시 확인

출력 결과는 vector<int>로 따로 관리 후 return

 

---

 

끝!