배열과 해시 대표 문제 풀기

이번 포스트에서는 leetcode에 있는 Array 와 Hashing의 대표 문제들을 풀어보겠습니다.

문제풀이는 편의상 C++로 진행하겠습니다. 

 

 

1. Containers Duplicates [Easy]

Contains Duplicate - LeetCode

풀이

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        // 이전에 나온 값을 저장하기 위해서 HashMap을 준비합니다.
        // Value는 int가 아니라 boolean으로 사용하셔도 됩니다.
        map<int,int> mp;
        
        // 배열을 순회하면서 이전에 방문한 적이 있는지 확인합니다.
        for (auto &x:nums) {
            // 만약 기록이 있으면 true를 반환합니다.
            if (mp.count(x)) {
                return true;
            }
            
            // 기록이 없으면 새로운 기록을 생성합니다.
            mp[x] = 1;
        }
        
        return false;
    }
};

 

 

2. Valid Anagram

Valid Anagram - LeetCode

풀이

class Solution {
public:
    bool isAnagram(string s, string t) {
        /* 
          Anagram은 같은 구성의 알파벳으로 이루어진 문자열을 의미합니다.
          즉, 문자열의 길이가 동일하고, 사용된 알파벳의 수가 동일합니다.
          따라서 아래와 같이 두 가지 방법으로 풀 수 있습니다.
          
          1. 두 문자열을 정렬하고 값을 비교합니다. O(NlogN), n은 문자열의 길이
          2. 문자열에 사용된 알파벳의 수를 저장하여 값을 비교합니다. O(N)
        
        */
        
        // 1번 방식으로 풀기
        // 문자열 s와 t를 정렬합니다.
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        return s == t;
    }
};

class Solution {
public:
    bool isAnagram(string s, string t) {
        /* 
          Anagram은 같은 구성의 알파벳으로 이루어진 문자열을 의미합니다.
          즉, 문자열의 길이가 동일하고, 사용된 알파벳의 수가 동일합니다.
          따라서 아래와 같이 두 가지 방법으로 풀 수 있습니다.
          
          1. 두 문자열을 정렬하고 값을 비교합니다. O(NlogN), n은 문자열의 길이
          2. 문자열에 사용된 알파벳의 수를 저장하여 값을 비교합니다. O(N)
        
        */
        
        // 2번 방식으로 풀기
        // s와 t에 사용된 알파벳의 개수를 저장하기 위한 배열을 생성합니다.
        // 이때 주의해야할 점은 제약사항중에 lowercase만 사용한다는 문구가 있어야 합니다.
        // 만약 uppercase까지 사용하는 경우에는 별도의 배열을 만들거나, 이중배열을 통해서 값을 구분해야합니다.
        vector<int> S(26,0), T(26, 0);
        
        
        // s에 들어간 알파벳의 개수를 저장합니다.
        for (auto &x:s) {
            S[x-'a']++;
        }
        
        // t에 들어간 알파벳의 개수를 저장합니다.
        for (auto &x:t) {
            T[x-'a']++;
        }
        
        // 배열을 순회하면서 값이 다른 알파벳이 있는지 확인합니다.
        for (int i = 0; i < 26; ++i) {
            
            // 사용된 알파벳 개수가 다르면 서로 다른 구성이기 때문에 false를 반환합니다.
            if (S[i] != T[i]) {
                return false;
            }
        }
        
        return true;
    }
};

근소한 차이이긴 하지만 두번째 풀이가 Runtime이 조금 빠른 것을 확인하실 수 있습니다.

 

3. Two Sum

Two Sum - LeetCode

풀이

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        const int n = (int)nums.size();
        
        // 배열을 이중으로 순회하면서 두 수를 더하여 target과 비교합니다.
        // 다만 Time Complexity가 O(N^2)이 되기 때문에, N값이 크면 TLE가 발생할 수 있습니다.
        for (int i = 0; i <n; ++i) {
            
            // i와 [i+1, n-1] 번째 수를 비교합니다.
            // 예를 들어, nums[0] 과 nums[1]을 비교한 이후에 nums[1]과 nums[0]을 비교할 필요가 없습니다.
            for (int j = i+1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return {i, j};
                }
            }
        }
        return {};
    }
};

위 풀이는 O(N^2)의 시간복잡도를 가지기 때문에 경우에 따라 시간 초과가 발생할 수 있습니다. 하지만 가장 기본적인 풀이라고 하더라고 알고계시면 좋습니다.

 

아래 풀이에서는 조금 더 개선해보겠습니다.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        const int n = (int)nums.size();
        
        // 이전에 사용된 숫자의 위치를 저장하기 위한 해시맵을 생성합니다.
        // key는 실제 값이고, value는 해당 값이 인덱스(위치) 입니다.
        unordered_map<int,int> mp;
        for(int i = 0; i<n; ++i) {
            // target - nums[i] 가 이전에 나왔는지 확인합니다.
            if (mp.count(target - nums[i])) {
                return {mp[target-nums[i]], i};
            }
            
            // 현재 숫자 정보를 입력합니다.
            mp[nums[i]] = i;
        }
        return {};
    }
};

위 풀이는 배열을 한 번만 순회하기 때문에 O(N)의 시간복잡도를 갖습니다. 하지만 해시맵 사용으로 O(N)의 공간 복잡도가 추가됩니다.

 

4. Group Anagrams

Group Anagrams - LeetCode

풀이

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        // Valid Anagram 문제를 확장한 문제입니다.
        // 배열을 돌면서 문자열을 정렬한 후에 같은 값인 것끼리 모아서 저장합니다.
        // 배열을 순회할 때마다 문자열을 정렬하기 때문에 N * KlogK 의 시간복잡도를 갖습니다. 
        
        // 같은 그룹을 저장하기 위한 해시맵을 생성합니다.
        map<string, vector<string>> mp;
        
        // 배열을 순회합니다.
        for (auto & x:strs) {
            // 먼저 문자열을 복사합니다.
            // 기존 문자열을 사용하면 원래 정보가 사라지기 때문에 복사한 후에 사용합니다.
            string b = x;
            
            // 복사한 문자열을 정렬합니다.
            sort(b.begin(), b.end());
            
            // 정렬한 문자열을 Key로 원래 문자열을 저장합니다.
            mp[b].push_back(x);
        }
        
        // 정답 배열을 생성합니다.
        vector<vector<string>> ans;
        
        // 기존에 Key별로 모았던 해시맵을 순회합니다.
        for (auto [k,v]:mp) {
            // 그룹리스트를 정답배열에 추가합니다.
            ans.push_back(v);
        }
        return ans;
    }
};

 

5. Top K Frequent Elements

Top K Frequent Elements - LeetCode

풀이

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // 빈도수를 저장하기 위해서 해시맵을 저장합니다.
        map<int, int> count;
        
        // 배열을 순회하면서 빈도수를 저장합니다.
        for (auto &x:nums) {
            count[x]++;
        }
        
        // 숫자와 빈도수의 pair를 저장하기 위한 배열을 생성합니다.
        vector<pair<int,int>> arr;
        
        // {빈도수, 값} 순서로 배열에 저장합니다.
        // 이유는 Sorting 시에 빈도수가 높은 순으로 해야하기 때문입니다.
        for (auto &[val, cnt]: count) {
            arr.push_back({cnt, val});
        }
        
        // 배열을 빈도수 기준으로 정렬합니다. rbegin(), rend()를 통해서 내림차순으로 정렬합니다.
        sort(arr.rbegin(), arr.rend());
        
        vector<int> ans;
        // K 번째까지만 정답에 추가합니다.
        for (int i = 0; i < k; ++i) {
            ans.push_back(arr[i].second);
        }
        return ans;
    }
};

 

6. Product of Array Except Self

Product of Array Except Self - LeetCode

풀이

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        const int n = (int)nums.size();
        
        // 전체 product에서 해당 값만 나누면 됩니다.
        // 다만 주의해야할 점이 nums[i] 가 0일 경우에는 0의 개수가 2개 이상인지 확인해야 합니다.
        // 만약 2개 이상이라면 모든 배열의 정답은 0이 됩니다.
        // 만약 1개 이하라면 nums[i] == 0 일 때 나머지 전체 값의 곱이 정답이 됩니다.
        
        // 0의 개수를 저장하기 위한 변수를 저장합니다.
        int zero_count = 0;
        
        // 전체 product를 계산하기 위해 값이 1로 초기화합니다.
        int product = 1;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 0) {
                zero_count++;
            } else {
                // 0이 아닌 경우에만 product를 계산합니다.
                product *= nums[i];
            }
        }
        
        vector<int> ans(n);
        for (int i = 0; i < n; ++i) {
            // 만약 0의 개수가 2개 이상이면 무조건 값이 0이 됩니다.
            if(zero_count > 1) {
                ans[i] = 0;
            } 
            // 0의 개수가 2개 미만이고, nums[i] == 0 이면 나머지 값의 product가 정답이 됩니다.
            else if (nums[i] == 0) {
                ans[i] = product;
            } 
            // nums[i] != 0 이고 0이 존재하면 값은 무조건 0이 됩니다.
            else if(zero_count > 0){
                ans[i] = 0;
            } 
            // 위 경우가 아닐때는 전체 결과를 자신의 값으로 나누면 됩니다.
            else {
                ans[i] = product / nums[i];
            }
        }
        return ans;
    }
};

위 코드를 0의 개수를 기준으로 로직을 구분합니다. 이런 경우에는 실수를 할 확률도 높고, 경우의 수를 놓치는 케이스가 발생할 수 있습니다. 0으로 나누는 것에 대해 주의해야하는 것도 하나의 걸림돌이 됩니다.

 

아래와 같이 다른 방법으로 풀어보겠습니다.

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        const int n = (int)nums.size();
        
        // 자신보다 앞에 있는 값들의 product를 prefix에 저장합니다.
        // 자신보다 뒤에 있는 값들의 product를 suffix에 저장합니다.
        vector<int> prefix(n, 1), suffix(n, 1);
        
        // prefix[i] 는 i-1번째까지 구한 값과 i-1번째 값을 구하면 됩니다.
        for (int i = 1; i < n; ++i) {
            prefix[i] *= prefix[i-1] * nums[i-1];
        }
        
        // suffix[i] 는 i+1번째까지 구한 값과 i+1번째 값을 구하면 됩니다.
        for (int i = n-2; i >=0; --i) {
            suffix[i] *= suffix[i+1] * nums[i+1];
        }
        
        vector<int> ans(n);
        
        // 배열을 순회하면서 자신의 앞과 뒤에 있는 결과를 곱하여 최종 product를 구합니다.
        for (int i = 0; i < n; ++i) {
            ans[i] = prefix[i] * suffix[i];
        }
        return ans;
    }
};

 

7. Encode and Decode Strings

Encode and Decode Strings - LeetCode

풀이

class Codec {
public:
    unordered_map<string, vector<string>> mp;
    // Encodes a list of strings to a single string.
    string encode(vector<string>& strs) {
        // 문자열의 조합을 위해 key string을 정의합니다.
        string key = "";
        
        // 각 문자열을 순회하면서 prefix "|" 와 문자열을 붙입니다.
        // prefix를 붙이는 이유는 조합이 같으면 key가 같아질 수 있기 때문입니다. 
        // 예를 들어 boy + star = boys + tar 로 구분이 안 될 수 있습니다.
        for (auto &s:strs) {
            key += "|" + s;
        }
        
        // 해당 Key에 원래 배열을 저장합니다.
        mp[key] = strs;
        return key;
    }

    // Decodes a single string to a list of strings.
    vector<string> decode(string s) {
        return mp[s];    
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.decode(codec.encode(strs));

 

8. Longest Consecutive Sequence

Longest Consecutive Sequence - LeetCode

풀이

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        // 문자열을 Sorting하기 위해서 set 을 생성합니다.
        set<int> s;
        
        // 전체 리스트를 저장합니다.
        for (auto &x:nums){
            s.insert(x);
        }
        
        // 만약 이전값과 현재값이 1 차이가 나면 길이를 1 늘려주고, 아니면 길이를 1로 초기화합니다.
        int prev = INT_MIN, ans = 0, curr = 0;
        for(auto &x:s) {
            if (prev == x - 1) {
                curr++;
            } else {
                curr = 1;
            }
            
            // 현재값과 최댓값을 비교하여 최댓값을 업데이트합니다.
            ans = max(ans, curr);
            
            // 이전 값을 업데이트합니다.
            prev = x;
        }
        return ans;
    }
};

---

배열 문제를 풀다보면 정렬 알고리즘을 사용하는 경우가 많습니다.

혹시 다양한 정렬 알고리즘을 알고 싶으신 경우, 아래 포스트도 한 번 읽어보시는 것을 추천드립니다.

[정렬] Insertion Sort(삽입 정렬) 기본 개념 및 관련 문제 풀기!

 

[정렬] Merge Sort 개념 정리 및 관련 문제 풀기