LeetCode - non-decreasing array

katanazero86·2020년 5월 26일
0

leetcode

목록 보기
4/13
post-thumbnail

non-decreasing array

  • Difficulty : easy

Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most 1 element.
We define an array is non-decreasing if nums[i] <= nums[i + 1] holds for every i (0-based) such that (0 <= i <= n - 2)

  • 정수가 n 인 배열의 숫자가 주어지면 최대 1 개의 요소를 수정하여 감소하지 않을 수 있는지 확인
  • nums [i] <= nums [i + 1]이 (0 <= i <= n-2)와 같이 모든 i (0 기반)에 대해 유지되는 경우 배열이 감소하지 않는 것으로 정의

example
Example 1:
Input: nums = [4,2,3]
Output: true
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.
Example 2:
Input: nums = [4,2,1]
Output: false
Explanation: You can't get a non-decreasing array by modify at most one element.

  • [2,3,3,2,4] : true / [3,3,2,2] : false -> 이 2가지 경우를 해결하면 된다!

solution

  • 작성 언어 : javascript
// 초기코드
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var checkPossibility = function(nums) {
        
};
  • leet code runtime 80 ms
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var checkPossibility = function(nums) {
    
    let changed = false;
 
    for(let i = 1; i < nums.length; i++) {
        if(nums[i] < nums[i-1]) {
            if(changed) {
                return false;
            }
            
            if(nums[i-2] > nums[i]) {
               nums[i] = nums[i-1];
               changed = true;
            } else {
               nums[i-1] = nums[i];        
               changed = true;
            }
        }
    }
    
    return true;      
    
};

  • 초기 작성 코드
  • leet code runtime 112 ms
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var checkPossibility = function(nums) {
    
    for(let i = 1; i < nums.length; i++) {
        if(nums[i] < nums[i-1] ) {       
            if(nums[i-2] > nums[i]) {
               nums[i] = nums[i-1];        
            } else {
               nums[i-1] = nums[i];        
            }
           break;
        }
    }
            
    if(!nums.some((num, index) => num > nums[index+1])){
        return true;
    } else {
        return false;
    }  
    
};
  • 처음에는 숫자를 1번 변경하고, some() 을 이용하여 조건을 검사하였다(Array.some() 메서드는 요소안에서 주어진 조건이 하나라도 true 면 true 를 반환한다)
  • 어찌보면 반복문을 2번 돌리는거와 같다;;
  • 초기코드를 제출하고 다른 성능이 좋은 답안을 보니, 1번 요소를 수정 후 또 같은 조건에 걸리면 감소가 되는거구나를 판단하여 바로 false 를 반환한다.
profile
developer life started : 2016.06.07 ~ 흔한 Front-end 개발자(현재는 백수 얏호👻)

0개의 댓글