TIL (2022.04.23)

Unordered_map

Ransome Note
이 문제는 magazine의 글자들로 ransomNote의 문자열을 만들어낼 수 있는지 없는지를 판별하는 것이였다.

input: ransomNote = "aa", magazine="ab"
output: false

이 문제를 보자마자 생각났던 방법은
hashMap을 쓰면 되지 않을까? 였다.

c++에서 hashmap 은 unordered_map

• map 보다 더 빠른 탐색이 가능
• 시간복잡도가 O(1), 최악의 경우 O(n)
• 자동으로 정렬되지 않음

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char,int> mp;
        for(auto ch:magazine){
            mp[ch]+=1;
        }
        for(auto rn : ransomNote){
            if(!mp[rn]) return false;
            mp[rn]-=1;
        }
        return true;
    }
};

Valid Anagram

t가 s의 anagram이면 true, 아니면 false

이론상으로는 unordered_map을 통해서 value의 개수를 카운트하고, 애너그램인지 아닌지를 판별하기 위해서 카운트에서 하나씩 빼줬다. 테스트코드는 맞게 나왔는데 왜 실전에서는 wrong answer가 뜨는 걸까 싶었다. 근데 생각해보니까 t와 s의 길이가 같아야 애너그램이 성립한다는 것을 까먹고 있었다. 부랴부랴 길이에 대한 판별문을 적어줬더니 통과가 떴다.

class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.length()!=t.length()) return false;
        else{
            unordered_map<char,int> mp;
            for(auto sch:s) mp[sch]+=1;
            for(auto tch:t) {
                if(!mp[tch]) return false;
                mp[tch]-=1;
            }
            return true;
        }
    }
};

First Unique Character in a String

input : s="loveleetcode"
output: 2

s의 문자열에서 처음으로 반복되지 않는 캐릭터를 찾으면 된다.
예를 들어, loveleetcode 에서는 v가 반복이 안되니까 인덱스값 2 리턴

class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char,int> mp;
        for (auto sch:s){
            mp[sch]+=1;
        }
        for(int i=0;i<s.length();i++){
            if(mp[s[i]]==1) return i;
        }
        return -1;
    }
};