[Leetcode] 665. Non-decreasing Array

May Leetcode Challenge 2021에서 5월 4일에 (PST) 출시된 문제를 풀어보도록 하겠다.

 

문제는 아래 링크를 참고하길 바란다.

leetcode.com/problems/non-decreasing-array/

Non-decreasing Array - LeetCode

이번에는 풀이보단 복기에 가까우니 참고해서 보시면 좋을 것 같습니다.

음, 결론부터 말하자면 이 문제를 제대로 풀진 못했다.

시간도 1시간 넘게 썼고... 운 좋게 이건가? 하고 때려맞췄는데, 그게 맞았다.

처음 문제 읽었을때는 너무 쉬워서 '넌 easy 겠구나' 하면서, 룰루랄라 코딩했다.

다 코딩하고 돌려보는데 역시는 역시. 오류를 뿜어내면서 계속 틀렸다.

그나마 처음에 고민했던 엣지케이스들 중에서 마지막에 영감을 얻어서 수정했는데 그게 맞았을 뿐, 제대로 이해하고 푼 것은 아니었다. easy 처럼 보인다고 너무 방심했다... 자만하지 말자...

---

우선 문제를 읽어보면 nums 라는 정수형 배열이 주어지고, 최대 1번의 원소를 수정해서 배열이 감소하지 않는 것으로 만들 수 있는지를 체크하는 것이다. 감소하지 않는다는 것의 정의는 nums[i] <= nums[i + 1] 이 모든 i 에 만족해야 한다는 것이었다. i 의 범위는 0 <= i <= n - 2 으로 주어졌다. (0-indexed)

 

또 결론부터 얘기하면 주어진 예시인 [4,2,3]과 [4,2,1] 은 페이크였다... 왜냐하면 비교는 적어도 4개로 해야 규칙을 알 수 있기 때문이다. 엣지케이스 위주로 로직을 점검해야 한다. 결국은 안되는 것만 걸러내면 되기 때문이다.

근데 예시처럼 케이스를 3개로 점검하다보면 한계가 무조건 생긴다. 왜냐하면 3개의 원소가 있을때는 3개 점에 의해 2개의 기울기만 생긴다. 2개의 기울기만 생기면 2번 연속 감소 밖에 체크할 수 없다. 1번 감소, n번 증가(0번 이상), 1번 감소의 케이스를 만족하기 위해서는 최소 3개의 기울기가 필요하고 그 말은 4개의 점이 필요하다는 뜻이다. 그래야 2번째 감소가 발생했을때 안되는 케이스를 체크할 수 있기 때문이다.

예를 들면서 설명하겠다. [4,3,2,1] 케이스를 보면 3번의 연속 감소가 있다. 이런 경우에는 쉽게 발견할 수 있다. 이 케이스는 0번 인덱스와 3번 인덱스 사이에 3번의 감소가 있는 케이스이다. 다음으로 [1,3,2,1] 케이스를 보면 1번의 증가 이후, 2번의 연속 감소가 있다. 이런 경우에도 명백하게 걸러낼 수 있다.

다음으로 [1,3,2,4] 케이스를 보자. 이 케이스에서는 (1 → 3) 으로 증가 이후에, (3 → 2) 로 감소를 하고, (2 → 4) 로 증가를 한다. 이런 경우에는 1번 인덱스 값인 3을 1 또는 2로 변경하거나, 2번 인덱스 값인 2를 3 또는 4로 변경해주면 된다.

그 다음으로 [2,3,1,4] 케이스를 보자. 이 케이스에서는 (2 → 3) 으로 증가 이후에, (3 → 1) 로 감소를 하고, (1 → 4) 로 증가를 한다. 2번 인덱스의 값인 1을 3 또는 4로 변경해주면 만족한다. 

마지막으로 [1,4,2,3] 케이스를 보자. 이 케이스에서는 (1 → 4) 로 증가 이후에, (4 → 2) 로 감소를 하고, (2 → 3) 으로 증가를 한다. 1번 인덱스의 값인 4를 1 또는 2로 변경해주면 만족한다.

문제는 [2,3,1,2] 나 [3,4,1,2] 같은 케이스이다. (2 → 3) 으로 증가 이후에 (3 → 1) 로 감소를 한 다음, 다시 (1 → 2) 으로 증가를 한다. (3 → 4) 로 증가 이후에 (4 → 1) 로 감소를 한 다음, 다시 (1 → 2) 으로 증가를 한다.

지금까지의 패턴을 보면 증가 → 감소 → 증가 패턴이라 당연히 성립할 것으로 예상할 수 있다. 하지만 이런 케이스는 2개 원소의 변경이 필요하므로 걸러내져야 하는 케이스이다. 이걸 걸러내기 위해 일반화를 시켜야 한다. [2,3,1,2] 에서 감소하는 지점을 확인하는 것은 3 → 1 로 넘어가는 과정이다. i 가 0-indexed라고 했으므로 필자는 i 를 기준으로 (i + 1) 의 값을 확인했다. 즉 [2,3,1,2] 에서 [i - 1, i, i + 1, i + 2] 로 두고 비교를 한 것이다. 여기서 nums[i - 1] 은 nums[i + 1] 보다 커야하고, nums[i] 는 nums[i + 2] 보다 커야한다는 2개의 명제를 만족하면 걸러내는 공식이 성립한다.

 

지금까지 걸러내야 할 예시들을 일반화 해보면 다음과 같다.

• nums[i] > nums[i + 1] 상황에서
  • 1번 더 동일한 상황 발생 (연속적이든 아니든)
  • nums[i - 1] > nums[i + 1] && nums[i] > nums[i + 2]

이 것을 토대로 코딩을 해보면 아래와 같다.

class Solution {
    public boolean checkPossibility(int[] nums) {
        int modifyCount = 1; // 총 수정 가능 횟수
        for (int i = 0; i < nums.length - 1; i++) { // 0-indexed
            if (nums[i] > nums[i + 1]) { // 감소하는 경우
                modifyCount--; // 수정 가능 횟수 1회 차감
                if (modifyCount < 0 // 감소 후 감소 발생, 첫번째 일반화 케이스
                 || (i > 0 && i < nums.length - 2 // 바운더리 체크
                 && nums[i - 1] > nums[i + 1] && nums[i] > nums[i + 2])) { // 두번째 일반화 케이스
                    return false;
                }
            }
        }
        return true;
    }
}

바운더리체크는 총 4개의 연속된 인덱스들을 비교해야하기 때문에, 현재 위치가 양끝에 존재하게 된다면 문제가 될 수 있기에 체크를 해주는 것이다. 

필자는 막힌 과정에서 문제를 다시 읽었는데 조건 중에 0 <= i <= n - 2 를 보고 깨달았다. 왜 n - 2 일까? 아, 이거 3개 비교 말고 1개 더 해야하는건가? 그렇게 조건을 추가해서 추적해서 찾을 수 있었다.

치열한 고민의 흔적... 이 페이지 초기화를 3번 정도 했던 것 같다.

그리고 이것저것 고민하면서 in-place 로 수정도 해보고 할텐데, in-place 로 수정하는 경우에도 4개를 기준으로 비교를 해야 정확하게 변경할 수 있다. 필자도 그렇게 구하는게 편할 것이라고 생각해서 in-place 로 풀었는데, 어차피 1번 탐색에 끝나고 true / false만 반환하면 끝나는 문제라서 in-place 는 큰 의미가 없다는 걸 깨달았다.

 

이 문제의 시간복잡도는 1번 탐색으로 완료되니 $O(n)$ 이다.

공간복잡도는 변수를 선언해서 따로 적재하는 행위를 하지 않았으니 $O(1)$ 이다.