문제 링크

내 코드

8ms, 126.79MB

GPT에게 질문한 코드.

class Solution {
public:
    vector<bool> isArraySpecial(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        vector<int> max_special_length = preprocess(nums); // Preprocessing 단계
        vector<bool> results;

        for (const auto& query : queries) {
            int left = query[0];
            int right = query[1];
            int range_length = right - left + 1; // 구간 길이 계산
            if (max_special_length[left] >= range_length) {
                results.push_back(true); // "special" 조건 만족
            } else {
                results.push_back(false); // "special" 조건 불만족
            }
        }
        return results;
    }
    vector<int> preprocess(const vector<int>& nums) {
        int n = nums.size();
        vector<int> max_special_length(n, 1);
        for (int i = n - 2; i >= 0; --i) {
            if ((nums[i] % 2) != (nums[i + 1] % 2)) { // 패리티가 다르면 길이 증가
                max_special_length[i] = max_special_length[i + 1] + 1;
            }
        }
        return max_special_length;
    }
};

Solution

Approach 1: Binary Search

• 38ms, 135.56MB
• Complexity
  • Let $M$ be the size of nums and $N$ be the size of queries.
  • Time Complexity: $O(M + N \cdot \log M)$
  • Space Complexity: $O(M)$

class Solution {
public:
    vector<bool> isArraySpecial(vector<int>& nums,
                                vector<vector<int>>& queries) {
        vector<bool> ans(queries.size());
        vector<int> violatingIndices;

        for (int i = 1; i < nums.size(); i++) {
            // same parity, found violating index
            if (nums[i] % 2 == nums[i - 1] % 2) {
                violatingIndices.push_back(i);
            }
        }

        for (int i = 0; i < queries.size(); i++) {
            vector<int> query = queries[i];
            int start = query[0];
            int end = query[1];

            bool foundViolatingIndex =
                binarySearch(start + 1, end, violatingIndices);

            if (foundViolatingIndex) {
                ans[i] = false;
            } else {
                ans[i] = true;
            }
        }

        return ans;
    }

private:
    bool binarySearch(int start, int end, vector<int>& violatingIndices) {
        int left = 0;
        int right = violatingIndices.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int violatingIndex = violatingIndices[mid];

            if (violatingIndex < start) {
                // check right half
                left = mid + 1;
            } else if (violatingIndex > end) {
                // check left half
                right = mid - 1;
            } else {
                // violatingIndex falls in between start and end
                return true;
            }
        }

        return false;
    }
};

GPT

아래 코드는 주어진 배열 nums에 대해 특정 구간이 “특별한(special)” 배열인지 빠르게 판단하기 위한 알고리즘입니다. “특별한” 배열이란 인접한 원소끼리 홀짝성(parity, 짝수/홀수)이 달라야 하는 배열을 의미합니다. 즉, 인접한 두 원소가 모두 짝수거나 모두 홀수이면 그 구간은 “특별하지 않다”고 볼 수 있습니다.

핵심 개념:

• 두 수가 인접해 있을 때, 둘의 홀짝이 같으면 그 인덱스를 “violation(위반)“이 발생한 인덱스로 기록합니다.
• 이후 특정 구간 [start, end]에 대해, 이 구간 안에 “violation”이 있으면 그 구간은 특별하지 않은 것이고, 없으면 특별한 구간입니다.
• 쿼리 처리 시 매번 직접 구간을 확인하는 대신, 미리 “violatingIndices”를 추려내고 이진 탐색으로 구간 내 위반 인덱스 존재 여부를 검사하여 효율적으로 답을 찾습니다.

코드 흐름:

1. violatingIndices 구성:

   for (int i = 1; i < nums.size(); i++) {
       if (nums[i] % 2 == nums[i - 1] % 2) {
           // i 인덱스의 원소와 i-1 인덱스의 원소가 홀짝이 같음
           violatingIndices.push_back(i);
       }
   }

   • nums 배열을 순회하면서 인접한 원소의 홀짝이 같은 경우, 그 인덱스 i를 violatingIndices에 넣습니다.
   • 예를 들어, nums = [1, 3, 2, 4]라면,
     • nums[0] = 1(홀수), nums[1] = 3(홀수) → 인덱스 1 추가
     • nums[1] = 3(홀수), nums[2] = 2(짝수) → 다름
     • nums[2] = 2(짝수), nums[3] = 4(짝수) → 인덱스 3 추가
   • 이렇게 하면 violatingIndices는 [1, 3]이 됩니다(예시).

2. 쿼리 처리: 각 쿼리는 [start, end] 구간이 주어집니다. 이 구간이 특별한지 확인하려면 이 구간 내에 “violatingIndices”에 기록된 인덱스가 있는지 확인하면 됩니다.

   for (int i = 0; i < queries.size(); i++) {
       int start = queries[i][0];
       int end = queries[i][1];
   
       bool foundViolatingIndex = binarySearch(start + 1, end, violatingIndices);
       // start+1을 사용하는 이유: 위반 인덱스 i는 i-1과 i사이의 위반이므로, 
       // 구간 내 인접 관계를 확인하려면 start+1부터 끝 인덱스까지 검사하면 됨.
       
       if (foundViolatingIndex) {
           ans[i] = false;  // 구간 내 위반 존재 → 특별하지 않다
       } else {
           ans[i] = true;   // 위반 없음 → 특별하다
       }
   }

   여기서 binarySearch 함수는 violatingIndices에서 [start+1, end] 범위 내의 위반 인덱스가 존재하는지 이진 탐색으로 검사합니다.

3. binarySearch 함수:

   bool binarySearch(int start, int end, vector<int>& violatingIndices) {
       int left = 0;
       int right = violatingIndices.size() - 1;
       while (left <= right) {
           int mid = left + (right - left) / 2;
           int violatingIndex = violatingIndices[mid];
   
           if (violatingIndex < start) {
               // 찾고자 하는 범위보다 왼쪽에 있으니 더 오른쪽을 탐색
               left = mid + 1;
           } else if (violatingIndex > end) {
               // 찾고자 하는 범위보다 오른쪽에 있으니 더 왼쪽을 탐색
               right = mid - 1;
           } else {
               // start <= violatingIndex <= end 범위 내 발견
               return true;
           }
       }
       return false; // 범위 내 위반 인덱스 없음
   }

   이진 탐색을 통해 violatingIndices 중 start 이상 end 이하에 해당하는 인덱스가 존재하는지 검사합니다.

정리:

• violatingIndices는 인접 원소가 홀짝이 같은 위치를 저장한 정렬된 배열입니다.
• 각 쿼리마다 이진 탐색을 통해 해당 구간에 위반 인덱스가 있는지 O(log n)에 확인할 수 있습니다.
• 위반 인덱스가 존재하면 그 구간은 특별하지 않다고(false), 없으면 특별하다고(true) 결과를 내놓습니다.

이러한 방식으로 여러 쿼리에 대해 빠르게 “특별한 배열인지”를 판단할 수 있습니다.

Approach 2: Prefix Sum

• 37ms, 136.56MB
• Complexity
  • Let $M$ be the size of nums and $N$ be the size of queries.
  • Time Complexity: $O(M + N)$
  • Space Complexity: $O(M)$

class Solution {
public:
    vector<bool> isArraySpecial(vector<int>& nums,
                                vector<vector<int>>& queries) {
        vector<bool> ans(queries.size(), false);
        vector<int> prefix(nums.size(), 0);
        prefix[0] = 0;

        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] % 2 == nums[i - 1] % 2) {
                // new violative index found
                prefix[i] = prefix[i - 1] + 1;
            } else {
                prefix[i] = prefix[i - 1];
            }
        }

        for (int i = 0; i < queries.size(); i++) {
            vector<int> query = queries[i];
            int start = query[0];
            int end = query[1];

            ans[i] = prefix[end] - prefix[start] == 0;
        }

        return ans;
    }
};

GPT

아래 코드는 “특별한 배열(special array)” 구간을 효율적으로 판별하기 위한 또 다른 접근 방식으로, Prefix Sum(누적 합) 기법을 활용한 예시입니다.

문제 개요 재정리:
인접한 두 원소가 모두 홀수거나 모두 짝수이면 “위반(violative)“이라고 합시다. 구간 [start, end]가 주어졌을 때, 이 구간 안에 위반이 전혀 없다면 그 구간은 “특별한” 구간입니다. 반면, 하나라도 위반이 있으면 특별하지 않은 구간이 됩니다.

접근 아이디어:
인접한 원소에서 위반이 발생하는 인덱스를 효율적으로 파악하기 위해, 각 인덱스별로 “지금까지 발생한 위반의 개수”를 prefix sum 형태로 기록합니다.

1. Prefix 배열 구성:

   vector<int> prefix(nums.size(), 0);
   prefix[0] = 0; 
   for (int i = 1; i < nums.size(); i++) {
       if (nums[i] % 2 == nums[i - 1] % 2) {
           // i 인덱스 위치에서 새로운 위반 발생
           prefix[i] = prefix[i - 1] + 1;
       } else {
           // 위반 없음
           prefix[i] = prefix[i - 1];
       }
   }

   여기서 prefix[i]는 0 ~ i 구간 사이에 존재하는 위반의 개수를 저장합니다.
   예를 들어, nums = [1,3,2,4]라면,

   • i=1: nums[1]=3, nums[0]=1 모두 홀수, 위반 발생 → prefix[1] = prefix[0] + 1 = 1
   • i=2: nums[2]=2 홀수 아님, nums[1]=3 홀수 → 서로 다른 홀짝, 위반 없음 → prefix[2] = prefix[1] = 1
   • i=3: nums[3]=4, nums[2]=2 모두 짝수, 위반 발생 → prefix[3] = prefix[2] + 1 = 2

   즉, prefix = [0,1,1,2]가 됩니다.

2. 구간 [start, end] 쿼리 처리:

   for (int i = 0; i < queries.size(); i++) {
       int start = queries[i][0];
       int end = queries[i][1];
   
       ans[i] = (prefix[end] - prefix[start]) == 0;
   }

   • prefix[end]는 0 ~ end 사이 위반 개수, prefix[start]는 0 ~ start 사이 위반 개수입니다.
   • prefix[end] - prefix[start]는 [start+1 ~ end] 구간 안에 발생한 위반의 개수를 의미합니다.
     왜 start+1부터냐면, 위반은 두 인접한 원소 사이에서 발생하므로, [start, end] 구간의 “인접 관계”는 start+1에서부터 확인됩니다.

   만약 prefix[end] - prefix[start] == 0이면, 해당 구간에는 위반이 없으므로 특별한 구간입니다.
   그렇지 않다면 하나 이상의 위반이 있다는 뜻이므로 특별하지 않은 구간입니다.

정리:

• prefix 배열을 통해 각 인덱스까지의 위반 개수를 저장해둡니다.
• 쿼리 시 prefix[end] - prefix[start]를 계산하여 구간 내 위반 여부를 O(1)에 판단합니다.
• 전체 알고리즘은 O(n)으로 prefix 계산 후, 각 쿼리를 O(1)에 처리할 수 있어 효율적입니다.

Approach 3: Sliding Window

• 50ms, 136.36MB
• Complexity
  • Let $M$ be the size of nums and $N$ be the size of queries.
  • Time Complexity: $O(M + N)$
  • Space Complexity: $O(M)$

class Solution {
public:
    vector<bool> isArraySpecial(vector<int>& nums,
                                vector<vector<int>>& queries) {
        int n = nums.size();
        vector<int> maxReach(n);
        int end = 0;

        // Step 1: Compute the maximum reachable index for each starting index
        for (int start = 0; start < n; start++) {
            // Ensure 'end' always starts from the current index or beyond
            end = max(end, start);

            // Expand 'end' as long as adjacent elements have different parity
            while (end < n - 1 && nums[end] % 2 != nums[end + 1] % 2) {
                ++end;
            }

            // Store the farthest index reachable from 'start'
            maxReach[start] = end;
        }

        vector<bool> ans(queries.size());

        // Step 2: Answer each query based on precomputed 'maxReach'
        for (int i = 0; i < queries.size(); i++) {
            vector<int> query = queries[i];
            int start = query[0];
            int end = query[1];

            // Check if the query range [start, end] lies within the max
            // reachable range
            ans[i] = end <= maxReach[start];
        }

        return ans;
    }
};

GPT

아래 코드는 “특별한 배열(special array)” 구간 판별을 위한 또 다른 접근 방식으로, 전처리(Precomputation) 를 통해 각 시작점에서 연속적으로 홀짝이 번갈아가며 나타나는 최대 구간의 끝 인덱스를 미리 계산한 뒤, 쿼리를 O(1)에 처리하는 방법을 구현한 예시입니다.

아이디어:

• 배열의 각 인덱스 start에 대하여, 이 인덱스부터 시작했을 때 인접한 원소들의 홀짝성이 번갈아 나타나는 최대 연속 구간의 마지막 인덱스 maxReach[start]를 구합니다.
• 이렇게 하면 구간 [start, end]가 주어졌을 때, 만약 end <= maxReach[start]면 해당 구간 내에서는 홀짝성이 계속 번갈아 나타난다는 뜻이므로 특별한 배열 구간입니다. 그렇지 않다면 중간 어딘가에서 홀짝 위반이 발생한 것입니다.

코드 해설:

1. maxReach 배열 계산:

   int n = nums.size();
   vector<int> maxReach(n);
   int end = 0;
   
   for (int start = 0; start < n; start++) {
       // end를 start 이상으로 이동
       end = max(end, start);
   
       // 인접한 원소들의 홀짝이 다를 동안 end를 오른쪽으로 확장
       while (end < n - 1 && nums[end] % 2 != nums[end + 1] % 2) {
           ++end;
       }
   
       // start에서 시작했을 때, 연속 홀짝 패턴이 이어질 수 있는 최댓값 end를 기록
       maxReach[start] = end;
   }

   동작 방식:

   • start 인덱스부터 시작하여 end를 오른쪽으로 움직이며 “홀짝 교차” 패턴이 깨지지 않는 한 계속 확장합니다.
   • 확장할 수 있는 만큼 확장한 뒤, maxReach[start] = end로 기록합니다.
   • 이렇게 하면 start에서 시작하는 구간 중 “특별한” 구간은 최대 end까지 유효합니다.

2. 쿼리 처리:

   for (int i = 0; i < queries.size(); i++) {
       int start = queries[i][0];
       int end = queries[i][1];
   
       // [start, end] 구간이 special한지 확인
       // special하려면 end가 maxReach[start] 이하여야 함
       ans[i] = end <= maxReach[start];
   }

   여기서 end <= maxReach[start]라면, start에서 시작하여 끝까지 홀짝 교차 패턴이 유지되는 최대 구간이 end 이상이라는 의미이므로, [start, end] 구간 내 위반 없이 “특별한” 구간입니다.
   반대로 end가 maxReach[start]보다 크다면, maxReach[start] 지점 이후 홀짝 패턴이 깨졌다는 뜻이므로 “특별한” 구간이 아닙니다.

복잡도:

• 전처리(maxReach 계산): O(n)
• 각 쿼리 처리: O(1)

따라서 여러 쿼리를 효율적으로 처리할 수 있습니다.
정리하자면, 이 코드는 각 시작점에서 최대한 홀짝성이 번갈아가며 나타나는 구간의 끝을 미리 계산해두고, 쿼리 시 즉각 판별하는 접근 방법입니다.