[C++][leetcode] Contiguous Array :: seoftware

 

---

 

"Time Limit Exceeded" 시간 초과가 난 코드

모든 가능한 경우의 수를 고려하려고 하니까 시간 초과가 발생한다. 

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int max_length = 0;
        for(int i = 0; i<nums.size(); i++){
            int sum = 0; int idx = 0;
            for(int j = i; j<nums.size(); j++){
                if(nums[j] == 0) sum -= 1;
                else sum += 1;
                
                if(sum == 0) idx = j;
            }
            if(idx>i) max_length = std::max(idx-i + 1, max_length);
        }
        return max_length;
    }
};

 

 

통과한 코드

hash_map unordered_map 해시맵 사용

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        unordered_map<int, int> map;
        map[0] = -1;
        int answer = 0;
        int sum = 0; 
        for(int i = 0; i<nums.size(); i++){
            sum += (nums[i]==0?-1:1);
            auto it = map.find(sum);
            if(it != map.end()) answer = std::max(answer, i-map[sum]);
            else map[sum] = i;
        }
        return answer;
    }
};

 

코드 이해를 위한 설명

0과 1로 이루어진 nums에서 0은 -1로 생각한다. 예시의 [ 0, 1, 0 ]은 [ -1, 1, -1 ]이 되는 것이다.

map은 어떤 숫자가 처음 나온 인덱스를 저장해주는 역할을 한다.

sum은 nums[0] 부터 nums[i] 까지의 합을 의미한다.

위의 [ -1, 1, -1 ]의 sum을 나타내면 [ -1, 0, -1 ]이다. 시작에 0이 있어야 다시 0이 나왔을 때 첫 번째 0부터 재등장한 0의 간격을 잴 수 있으므로 map[0] = -1로 설정해준다. 0이 처음 나오는 인덱스가 -1이라는 의미이다. 

map[0] = -1로 함으로써 sum을 [ 0, -1, 0, -1 ]로 나타낼 수 있다. 따라서 두번 이상 등장하는 숫자가 0과 -1 두 개가 있다. 0과 0사이의 간격은 2이고, -1과 -1의 간격도 2이므로 가장 큰 간격은 2가 된다.

위를 구할 때 매 인덱스(i)마다 sum을 구한다. 그 값이 map에 존재하면 지금 값과의 차이를 구해서 answer과 비교하고 더 큰 값을 answer에 저장한다. map에 존재하지 않는다면 i 값을 map[sum] 에 저장한다.

 

find는 해당 원소가 map에 존재하면 첫번째로 일치하는 반복자를 리턴하고, 존재하지 않으면 마지막 last 원소를 리턴한다.

따라서, find 함수로 원소를 찾은 후 그것이 map.end()와 다르면 map에 찾는 원소가 있는 것이고,
map.end()와 같다면 map에 찾는 원소가 없는 것이다.