665. Non-decreasing Array

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

Non-decreasing Array - LeetCode

이 문제 한 이틀 고민했는데, 안 풀린 문제였습니다.

 

분명, 어제만해도 굉장히 쉽게 문제를 풀어서 기분이 좋았는데, 왜.... 이렇게 됐죠.

ㅠ

제가 실패한 부분은 서로 다른 환경에서 어떻게 대처를 해야하는지에 대한 미숙함이었습니다. 즉, 문제 분석이라 생각합니다.

 

문제를 분석하기 위해선, 두 가지가 필요하다 생각하는데 집중력과 시간이라 생각합니다. 집중력이 좋아도 시간이 부족해서 아이디어가 안 떠오를 수 있고, 시간이 많아도 집중력이 좋지 않다면 아이디어가 떠오르지 않겠죠. 전 후자의 경우였습니다.

 

버스에서 문제보고, 쉬는시간에 문제보고, 화장실에서 문제보고, 밥 먹으면서 문제를 보면서 풀어봤는데, 그냥 책상 앞에서 집중한다는 마음가짐으로 문제를 분석하는 것이 최고인거 같네요.

 

자 그럼 문제를 풀어보도록 합시다.

class Solution(object):
    def checkPossibility(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        cnt = 0
        for i in range(len(nums) - 1):
            if nums[i] > nums[i + 1]:
                if cnt:
                    return False
                cnt += 1
                if i == 0:
                    nums[i] = float('inf')
                elif nums[i - 1] < nums[i + 1]:
                    nums[i] = nums[i - 1]
                elif nums[i - 1] > nums[i + 1]:
                    nums[i + 1] = nums[i]
        else:
            return True

본 문제는 굉장히 많은 Edge Case를 가지고 있습니다.

 

[4, 2, 3] ==> 4를 1로 바꾸면 됩니다.

[3, 4, 2, 5] ==> 2를 4로 바꾸면 됩니다.

[-1, 4, 2, 3] ==> 4를 2로 바꾸면 됩니다.

 

되게 간단해보이죠? 막상 풀어보면 비교를 어느 순간에 해야할지 굉장히 헷갈리실 겁니다.

 

그래서 저는 두 수의 비교 후 필요한 경우 3가지 수를 비교하여 기울기를 맞춰주는 방식으로 진행했고, 그 상황이 2번 이상 발생하면 False를 return 했습니다.

---

사실 이 문제의 경우 총 2가지 문제 풀이 방법이 있습니다.

 

제가 했던 한 가지의 방법과 전체 탐색 (Brute Force)

 

Brute Force 방법의 경우 간단합니다. 하나의 수를 바꿔보고 그 배열이 정답을 만족하는지 확인, 아니면 다시 되돌려놓고 그 다음 수를 바꿔보고 다시 확인 .... 쭉 ....

 

당연히 효율을 원하는 코딩테스트에서 좋은 결과를 얻지 못하겠죠.

 

그래서 제가 했던 방법을 사용한 것입니다.

 

저 역시 제대로 문제를 해결하지 못해서 아쉬운 문제였지만, 덕분에 공부를 할 땐 책상에 앉아서 제대로 해야한다는 것을 깨우치게 해준 문제였습니다.

 

흑.. 바쁜 걸 어떡해 ㅠㅠ

---

이상 665. Non-decreasing Array였습니다.