Problem
주어진 배열의 원소 하나만 바꿔서 Non-decreasing Array 를 만드는 문제입니다.
문제에서 정의하는 Non-decreasing Array 란 그냥 오름차순 배열을 의미합니다.
Solution
생각보다 실수하기 쉬운 문제입니다.
우선 for
문을 돌면서 increasing
구간을 찾습니다.
하나도 없으면 true
를 리턴하고, 두 개 이상 나온다면 false
를 리턴합니다.
만약 increasing
구간이 한 개라면 nums[i]
와 nums[i + 1]
중 하나를 바꿔줘야 합니다.
nums[i]
만 바꿨을 때의 반례 :[5,7,1,8]
nums[i + 1]
만 바꿨을 때의 반례 :[4,2,3]
그래서 nums[i]
를 바꾼 경우의 배열 과 nums[i + 1]
를 바꾼 경우의 배열 두 가지를 각각 만들어서 체크해야 합니다.
하지만 배열을 두개나 만들어서 또 체크하는 건 시간적으로나 공간적으로 비효율적입니다.
우선 두 가지 사실을 생각해야 합니다.
nums[i]
값은 다음 차례에서는 확인하지 않는다.nums[i]
값은nums[i -1]
보다 커야한다.
1 번을 예를 들면 nums[0]
과 nums[1]
을 비교하고 난 후에는 nums[1]
과 nums[2]
만 비교합니다.
nums[0]
은 바뀌든 말든 의미가 없기 때문에 굳이 바꿔줄 필요가 없습니다.
2 번은 nums[i]
값과 nums[i + 1]
값 중 어느 값을 바꿔야 할지 결정할 수 있게 해줍니다.
결국 두 값 중 하나를 바꿔줘야 하는데 이걸 비교하는 시점에서는 nums[i] > nums[i + 1]
조건이 보장된 상태입니다.
만약 nums[i - 1] > nums[i + 1]
인데 nums[i] = nums[i + 1]
처리를 해버리면 무조건 false 상태가 됩니다.
nums = [10, 15, 5]
nums[i - 1] = 10
nums[i] = 15
nums[i + 1] = 5
// 설명
nums[i] 와 nums[i + 1] 중 하나를 무조건 바꿔줘야 하는데
nums[i] 를 5 로 바꿔버리면 nums[i - 1] 보다 작아진다.
Java Code
class Solution {
public boolean checkPossibility(int[] nums) {
boolean modified = false;
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] > nums[i + 1]) {
if (modified) return false;
modified = true;
// 다음에 비교할 nums[i + 1] 값만 바꿔주면 됨
if (i > 0 && nums[i - 1] > nums[i + 1]) {
nums[i + 1] = nums[i];
}
}
}
return true;
}
}
'알고리즘 문제 > LeetCode' 카테고리의 다른 글
[LeetCode Easy] Partition Array Into Three Parts With Equal Sum (Java) (2) | 2021.04.08 |
---|---|
[LeetCode Easy] Add Binary (Java) (0) | 2021.04.08 |
[LeetCode Easy] Last Stone Weight (Java) (0) | 2021.04.01 |
[LeetCode Easy] Maximum Number of Balloons (Java) (0) | 2021.03.31 |
[LeetCode Medium] Binary Tree Level Order Traversal (Java) (0) | 2021.01.03 |