Daily Leetcoding Challenge 896. Monotonic Array

LeetCode - The World's Leading Online Programming Learning Platform

직관

monotonic array란 주어진 배열 nums가 단조 증가(모든 i <= j 에 대해 nums[i] <= nums[j])하거나 단조 감소(모든 i <= j 에 대해 nums[i] >= nums[j])하는 경우를 말한다. monotonic한 배열인지 확인하려면 배열의 모든 값을 확인할 수밖에 없다.

접근법

코드만 봤을 때는 두 번째가 깔끔하고 빠르기도 빠를 것 같은데 코드를 제출 했을 때는 첫 번째 솔루션이 더 빠르게 나왔다. 아마도 테스트 케이스 중에 단조 증가하는 경우가 많아서 첫 번째 루프까지만 돌아서 런타임이 짧게 나오는 것 같다.

첫 번째 방법 (99.88%)

배열을 순회하면서 단조 증가하는 경우를 먼저 확인하고, 단조 증가하면 true를 반환한다.

배열을 순회하면서 단조 감소하는 경우를 확인한다. 단조 감소하면 true를 반환한다.

두 번째 방법 (32.29%)

배열을 순회하면서 단조 증가(inc &= nums[i] <= nums[i+1]), 단조 감소(dec &= nums[i] >= nums[i+1])을 계산한다.

inc || dec (단조 증가 또는 단조 감소하면 true)를 반환한다.

복잡도

두 코드 모두 시간 복잡도는 O(n)이고 공간 복잡도는 O(1)이다.

코드

99.88%인 코드 (1ms)

class Solution {
    public boolean isMonotonic(int[] nums) {
        boolean mono = true;
        for(int i=0; i<nums.length-1; i++) {
            if (nums[i] > nums[i+1]) {
                mono = false;
                break;
            }
        }
        if (mono) {
            return mono;
        }
        
        mono = true;
        for(int i=0; i<nums.length-1; i++) {
            if (nums[i] < nums[i+1]) {
                return false;
            }
        }
        return true;
    }
}

32.29%인 코드 (3ms)

class Solution {
    public boolean isMonotonic(int[] nums) {
        boolean inc = true, dec = true;
        for(int i=0; i<nums.length-1; i++) {
            inc &= nums[i] <= nums[i+1];
            dec &= nums[i] >= nums[i+1];
        }
        return inc || dec;
    }
}