[LeetCode] - 896. Monotonic Array

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Monotonic Array" 문제입니다.

--> https://leetcode.com/problems/monotonic-array/description/

 

문제 : 

An array is monotonic if it is either monotone increasing or monotone decreasing.

An array nums is monotone increasing if for all i <= j, nums[i] <= nums[j].

An array nums is monotone decreasing if for all i <= j, nums[i] >= nums[j].

Given an integer array nums, return true if the given array is monotonic, or false otherwise.

---

Example 1 :

Input : nums = [1,2,2,3]

Output : true

 

Example 2 :

Input : nums = [6,5,4,4]

Output : true

 

Example 3 :

Input : nums = [1,3,2]

Output : false

 

Constraints :

• 1 <= nums.length <= 10^5
• -10^5 <= nums[i] <= 10^5

---

주어진 정수 배열 nums가 단조 배열(monotonic array)인지 확인하는 문제입니다. 단조 배열이란 다음 두 조건 중 하나를 만족하는 배열을 말합니다 :

1. 단조 증가 배열 (Monotone Increasing) : 모든 i <= j에 대해 nums[i] <= nums[j]를 만족하는 배열.
2. 단조 감소 배열 (Monotone Decreasing) : 모든 i <= j에 대해 nums[i] >= nums[j]를 만족하는 배열.

주어진 배열 nums가 단조 배열이라면 true를 반환하고, 그렇지 않다면 false를 반환합니다.

 

class Solution{
    public boolean isMonotonic(int[] nums){
        boolean decreasing = true;
        boolean increasing = true;
        

        for(int i = 1; i < nums.length; i++){
            if(nums[i] < nums[i-1]){
                increasing = false;
            }
            if(nums[i] > nums[i-1]){
                decreasing = false;
            }
        }

        return increasing || decreasing;
    }
}

 

코드 설명을 드리자면 : 

 

 

 

1. 플래그 초기화 :
   • decreasing와 increasing은 각각 배열이 단조 감소 및 단조 증가인지 추적하는 플래그입니다. 초기값은 true로 설정하여 조건 검사를 시작합니다.
      
2. 배열 순회 :
   • 배열의 첫 번째 요소부터 끝까지 순회합니다. (i = 1에서 시작하여 이전 요소와 비교합니다.)
   • nums[i] < nums[i-1]이면 배열이 단조 증가가 아님을 나타내며 increasing을 false로 설정합니다.
   • nums[i] > nums[i-1]이면 배열이 단조 감소가 아님을 나타내며 decreasing을 false로 설정합니다.
3. 결과 반환 :
   • 배열이 단조 증가나 단조 감소 중 하나라도 참이라면 true를 반환합니다.
   • 두 플래그 중 하나라도 true면 배열은 단조 배열입니다. 그렇지 않으면 false를 반환합니다.

시간 복잡도

• O(n) : 배열 nums를 한 번 순회하기 때문에 시간 복잡도는 O(n)입니다. 여기서 n은 배열의 길이입니다.

공간 복잡도

• O(1) : 추가적인 데이터 구조를 사용하지 않고, 두 개의 불리언 변수를 사용하므로 공간 복잡도는 O(1)입니다. 이는 상수 공간 사용을 의미합니다.

---

하지만, 여기서 조건문을 조금만 더 개량하면 더 나은 코드가 될 수 있습니다 : 

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

 

이 코드는 주어진 배열이 단조 배열인지 확인하기 위해 두 가지 케이스를 고려합니다: 배열이 단조 증가인지, 혹은 단조 감소인지. 각각의 경우에 대해 배열을 한 번만 순회하여 단조성을 확인합니다.

1. 시작과 끝 요소 비교 :
   • nums[0]이 nums[nums.length-1]보다 작으면 배열이 단조 증가일 가능성을 염두에 두고 체크합니다.
   • 그렇지 않으면 배열이 단조 감소일 가능성을 염두에 둡니다.
2. 단조 증가 검사 :
   • 배열이 단조 증가일 경우, 각 요소가 이전 요소보다 작으면 false를 반환합니다.
3. 단조 감소 검사 :
   • 배열이 단조 감소일 경우, 각 요소가 이전 요소보다 크면 false를 반환합니다.
4. 결과 반환 :
   • 모든 조건을 만족하면 true를 반환하여 배열이 단조 배열임을 확인합니다.

전 코드와의 차이점

• 개선점 :
  • 코드 단순화 : 이전 코드에서는 두 개의 불리언 플래그(increasing, decreasing)를 사용하여 증가 및 감소 여부를 동시에 체크했지만, 이 코드는 시작과 끝 요소를 비교하여 한 번의 순회로 증가 또는 감소를 별도로 확인합니다.
  • 빠른 종료 : 단조 증가 또는 단조 감소 중 하나를 확인한 후, 배열 순회 중 조건이 맞지 않으면 즉시 false를 반환하여 불필요한 연산을 줄입니다.

결론적으로...

이 코드는 두 가지 경우를 나누어 배열이 단조 증가인지 또는 단조 감소인지를 더 명확하게 검사합니다. 첫 번째와 마지막 요소의 크기를 비교함으로써 배열의 성향을 파악하고, 그에 따라 한 번의 순회로 단조성을 확인합니다. 이러한 개선으로 인해 코드의 가독성과 성능이 향상되었습니다.

특히, 이 코드는 배열이 증가 혹은 감소인지 명확하게 구분하여 불필요한 조건 검사를 최소화하고, 빠른 종료를 통해 연산 효율성을 높이는 장점이 있습니다. 이로써 단조성 확인 작업을 더욱 효율적으로 수행할 수 있습니다.

---

개선 되기 전 후 Runtime 결