Sho1007

MMORPG 클라이언트 개발자 지망생

2 minute read

2762. Continuous Subarrays / c++ / Medium / 2시간+

문제 및 코드

#include <set>

inline int MAX(int a, int b) { return a > b ? a : b; }
inline int MIN(int a, int b) { return a < b ? a : b; }
inline int ABS(int a) { return a >= 0 ? a : -a; }
class Solution {
public:
    long long continuousSubarrays(vector<int>& nums) {
        long long answer = 0;
        int n = nums.size();
        int left = 0, right = 0;
        multiset<int> ms;

        while (left < n)
        {
            while (right < n)
            {
                if (!ms.empty())
                {
                    int minNum = MIN(*ms.begin(), nums[right]);
                    int maxNum = MAX(*ms.rbegin(), nums[right]);

                    if (ABS(minNum - maxNum) > 2) break;
                }
                ms.insert(nums[right++]);
            }
            answer += right - left;
            ms.erase(ms.find(nums[left++]));
        }

        return answer;
    }
};

접근 방식

투 포인터

  1. 배열 nums의 부분 배열 중 모든 원소의 차이의 절대값이 2보다 작거나 같은 부분배열의 갯수를 반환하는 문제
  2. 처음엔 원소의 개수에 따른 부분 배열의 개수를 저장하는 continuous 벡터를 사용했다. (ex. 원소가 1개인 부분배열이 2개라면 continuous[1] = 2)
  3. i로 1번 순회하면서 다시 j = i부터 2차 순회한다.
    1. 모든 nums[j]에 대해 min, max 값을 초기화해준다.
    2. max - min > 2 이면 break;
    3. 2번이 아니라면, (j - i + 1)개의 원소를 가지는 부분 배열이 하나 새로 생긴 것이므로 continuous[j - i + 1]++;
  4. 이런식으로 한 뒤, continuous의 모든 원소를 다 더한 값을 반환
  5. 하지만 이 방법은 시간초과가 났었다. (지금 생각해보면 매번 i부터 시작해서 부분 배열을 만들 필요가 없었다.)
  6. 여러 방법을 시도해봤지만 해결하지 못했고, 다른 사람들의 접근법을 참고했다.
  7. 요점은 투 포인터였다, 내가 시도했던 방법은 원 포인터 i에 대해 2차 순회를 통해 매번 부분 배열을 만들었던 반면, 투 포인터를 쓰게 되면
    1. left부터 right까지의 부분 배열을 구한다. (시작은 둘 다 0), left < nums.size()로 1차 반복, 그 안에서 right < nums.size()로 2차 반복한다.
    2. 새로운 원소를 넣을 때 min, max 검사를 해주고 (이 때, multiset을 사용하여 begin(), rbegin()으로 부분 배열의 최소, 최대값을 가져올 수 있다.)
    3. 조건에 만족한다면 부분 배열에 넣고, right를 1 증가
    4. 조건에 만족하지 못한다면 answer에 거기까지의 부분배열의 개수 (해당 부분 배열의 원소 수, 여기서는 right - left)를 더해준다.
    5. 그리고 부분 배열에서 nums[left] 원소를 빼주고, left를 1 증가
    6. 2중 반복이 모두 완료되면, answer를 반환
  8. 해결

생각해 볼 점

  1. 요즘 나오는 스택 / 큐 카테고리의 문제들이 꽤나 어렵다. (그리고 스택 / 큐를 활용한 풀이법도 모르겠고 다른 알고리즘을 사용해서 풀게 된다.)
  2. 어떤 배열의 연속된 부분 배열의 개수는 그 배열의 원소의 수였다. (ex. [1, 2, 3, 4]의 경우 [1], [1, 2], [1, 2, 3], [1, 2, 3, 4]의 부분 배열이 있는데, 이는 배열의 원소의 개수인 4와 동일하다.)
  3. 첫 번째 풀이법에서 시간초과가 났었는데, 그 때 만들어둔 부분 배열을 초기화 하지 않고, 해당 배열에서 left 원소만 제거하고 다시 이어나갔어야했다. (사실 이게 투 포인터의 핵심 원리, 그 때는 투 포인터라고 생각하지 않고 접근해서 이 방법을 생각하지 못했다.)

해시태그

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL

You may also enjoy