(C++) - LeetCode (easy) 697. Degree of an Array

https://leetcode.com/problems/degree-of-an-array/description/

Degree of an Array - LeetCode

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

📕 풀이방법

📔 입력 및 초기화

degree, 정답 변수 length, 현재 num을 key로하고 value를 해당 num이 나온 index들의 vector로 map idxOfNumsMap을 선언해 값들을 저장해줍니다.

📔 풀이과정

1. nums = [1, 2, 2, 3, 1] 이라면 idxOfNumsMap에는 다음과 같이 저장되어 있습니다.

{1, {0, 4}}

{2, {1, 2}}

{3, {3}}

이 형태를 보고 map value부분의 size는 곧 해당 key의 빈도수임을 알 수 있습니다.

따라서 idxOfNumsMap의 원소들을 순회하며 value.size()의 max값을 degree에 저장해줍니다.

2. subarray는 map value의 처음원소와 끝 원소의 차이로 최소 길이를 구할 수 있으므로 다시 순회하며 해당 값의 최소를 length에 저장해줍니다.

📔 정답 출력 | 반환

length를 반환합니다.

---

📕 Code

📔 C++

class Solution {
public:
    int findShortestSubArray(vector<int>& nums) {
        int degree = 0;
        int length = 0x3f3f3f3f;
        map <int ,vector<int>> idxOfNumsMap;

        for(int i = 0; i < nums.size(); i++) {
            idxOfNumsMap[nums[i]].push_back(i);
        }
        
        for(auto im : idxOfNumsMap) {
            int curFreq = im.second.size();
            degree = max(degree, curFreq);
        }

        for(auto im : idxOfNumsMap) {
            int curFreq = im.second.size();
            if(degree == curFreq) {
                vector <int> idxs = idxOfNumsMap[im.first];
                length = min(length, idxs[idxs.size() - 1] - idxs[0] + 1);
            }
        }
        return length;
    }
};

---

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