Sho1007

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

2 minute read

2145. Count the Hidden Sequences / c++ / Medium / 47분

문제 및 코드

#include <iostream>
using namespace std;

class Solution {
public:
    int numberOfArrays(vector<int>& differences, int lower, int upper) {
        if (differences.size() == 0)
        {
            return upper - lower + 1;
        }

        int minNum = differences[0], maxNum = differences[0];
        long long current = 0;
        for (int i = 0; i < differences.size(); ++i)
        {
            current += differences[i];
            if (current > maxNum)
            {
                maxNum = current;
            }
            if (current < minNum)
            {
                minNum = current;
            }
        }

        int newLower = lower - minNum;
        if (newLower < lower) newLower = lower;
        int newUpper = upper - maxNum;
        if (newUpper > upper) newUpper = upper;

        // cout << newLower << ' ' << newUpper << '\n';

        if (newUpper < newLower) return 0;

        return newUpper - newLower + 1;
    }
};

접근 방식

배열

  1. 어떤 배열의 인접한 두 원소의 차이를 기록한 differences 배열과, 원소의 최소값 기준 lower, 최대값 기준 upper 가 주어졌을 때, 이 조건을 만족하는 배열의 개수를 반환하는 문제였다.
  2. 우선 0-indexed였으므로, differences의 원소의 갯수가 0개인 경우를 상정했다.
  3. 이 경우, (upper - lower + 1) 이 가능한 배열의 개수였다.
  4. 다음으로 differences 배열에 원소가 있는 경우에도 3번 식을 적용할 수 있었는데, 내 생각은 모든 경우를 다 따질게 아니라, 0을 기준으로 differences를 순회하며 차이값들을 다 적용해보고, 그 중 최소값과 최대값을 찾아서 활용하는 것이었다.
  5. 예를 들어, 기존 upper 가 4 인데, 0을 기준으로 찾은 배열의 최대값이 10인 경우, 배열은 최소 -6으로 시작해야한다. (그래야 최대값 10이 나오는 시점에 시작값이 0이 아닌 -6이므로, 10-6 = 4가 되어, 기존의 upper를 충족한다.)
  6. 즉 조건을 만족하기 위한 시작값의 새로운 최대값 기준 newUpper, newLower을 위의 식처럼 계산하여 구한다.
  7. 그리고 newUpper가 newLower보다 작으면 (같을 땐 최소 만족하는 원소가 1개라도 있음) 0을 반환, 크거나 같으면 newUpper - newLower + 1을 반환한다. (3번식과 유사)
  8. 하지만 여기서 문제가 생겼다. 이건 leetcode의 좋은 점이자 안좋은 점인데, 틀리면 틀린 케이스를 보여준다는 것이다. 내가 발견한 문제점은 newUpper가 기존의 upper보다 큰 경우였다. (이러면 7번식으로 계산한 값이 upper을 초과하여 조건이 성립하지 않는다.)
  9. 그래서 생각해낸게, newUpper가 upper를 초과하면, newUpper 값 대신 upper 값을 쓰는 것이었다. (newLower도 마찬가지)
  10. 그렇게 수정했더니 통과했다.

생각해 볼 점

  1. 배열의 규칙 (최대값 - 최소값 + 1)을 찾아서 해결한 문제라 뿌듯했다.
  2. 0-indexed 문제는 해결했는데, newUpper가 upper보다 커질거라고는 생각하지 못했다. 만약 실제 코딩 테스트였다면 왜 틀렸는지 몰랐을 것이다. (이런 부분을 잘 찾아내는게 중요하다는걸 다시 한번 느낀다.)
  3. 중간에 minNum,maxNum 을 구할 때, int의 범위를 넘어가서 long long 으로 바꿔서 해결했다. (배열의 차이값을 저장한 differences의 원소가 int라고 해서, 실제 배열의 원소도 int일거라고 생각한게 실수였다.)
  4. 여러모로 자료형과 제한 범위에 대해 생각해 볼 수 있는 문제였다.

해시태그

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

You may also enjoy