(C++) - LeetCode (easy) 594. Longest Harmonious Subsequence

https://leetcode.com/problems/longest-harmonious-subsequence/description/

Longest Harmonious Subsequence - LeetCode

자료구조를 이용한 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

1. map numsMap을 선언 후 key에는 nums의 원소를, value에는 해당 원소의 빈도 수를 저장해줍니다.2. 정답 vector hs를 선언해 줍니다.3. vector pair<int,int> v를 선언해 numsMap의 key, value를 각각 first, second에 옮겨줍니다.4. 이미 map에서 옮긴 v의 원소에 대해 for loop를 수행합니다. first에대해 정렬되어 있으므로 이웃한 원소는 최소 차이를 가집니다. 1차이나는 상황에서 빈도수의 최대합인 maxFre를 선언 후 저장해줍니다.

 

📔 풀이과정

1. v에 대해 for loop를 수행하며 maxFre인 경우 one과 two 변수에 각 원소의 first를 저장해줍니다.2. nums에 대해 for loop를 수행하며 찾은 one, two값들을 hs에 넣어줍니다.

📔 정답 출력 | 반환

hs.size()를 반환합니다.

---

📕 Code

📔 C++

using pii = pair<int,int>;
class Solution {
public:
    int findLHS(vector<int>& nums) {
        vector <int> hs;
        map <int, int> numsMap;
        for(auto n : nums) {
            numsMap[n]++;
        }

        vector <pii> v;
        
        for(auto n : numsMap) {
            v.push_back({n.first, n.second});
        }
        int maxFre = 0;
        for(int i = 0; i < v.size() -1; i++) {
            if(abs(v[i].first - v[i+1].first) == 1)
                maxFre = max(maxFre, v[i].second + v[i+1].second);
        }
        int one, two;
        for(int i = 0; i < v.size() -1; i++) {
            if(maxFre == v[i].second + v[i+1].second) {
                one = v[i].first;
                two = v[i+1].first;
                break;
            }
        }
        for(auto n : nums) {
            if(n == one || n == two) {
                hs.push_back(n);
            }
        }
        return hs.size();
    }
};

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.