[LeetCode-665] 위반이 1번이어도, '고칠 수 있는지'는 따로 확인해야 한다
- 문제 링크: https://leetcode.com/problems/non-decreasing-array/
- 파일 경로:
src/main/java/coding_test/배열_리스트/LC0665_NonDecreasingArray.java - 난이도: Medium
문제 설명
정수 n개로 이루어진 배열 nums가 주어진다. 원소를 최대 한 번만 수정해서 비내림차순(nums[i] <= nums[i+1]이 모든 i에서 성립)으로 만들 수 있으면 true, 없으면 false를 반환한다.
1
2
3
4
5
Input: nums = [4,2,3]
Output: true // 첫 번째 4를 1로 바꾸면 [1,2,3]
Input: nums = [3,4,2,3]
Output: false // 어느 원소 하나를 바꿔도 안 됨
시행착오
1909(Remove One Element)에서 썼던 “위반 횟수 세기” 뼈대를 그대로 가져와서 시작했다. nums[i-1] > nums[i]인 지점을 downCount로 세고, 그 지점의 인덱스를 idx에 저장했다.
여기서부터 여러 단계로 헤맸다.
- 죽은 코드: 처음엔 위반을 찾은 직후에
if (i > 1 && nums[i-1] <= nums[i] && ...)처럼, 방금else분기(즉nums[i-1] > nums[i]가 확정된 상태)에서 다시nums[i-1] <= nums[i]를 확인하는 조건을 넣었다. 이건 그 시점에 절대 참이 될 수 없는 죽은 코드였다(941에서 겪었던 것과 같은 유형의 버그). - 비교 대상이 틀림: “앞을 낮출 수 있는지” 확인하려면 위반 지점 앞앞(
idx-2)과 비교해야 하는데, 계속idx-1과 비교하고 있었다. - AND/OR가 뒤집힘: “앞을 낮출 수 있다”와 “뒤를 올릴 수 있다”를
&&로 묶어서 둘 다 가능할 때만 고칠 수 있다고 판단했다. 실제로는 둘 중 하나만 가능해도 충분한데(수정 기회가 하나뿐이니, 두 옵션 중 하나만 성공하면 된다), 이걸 반대로 짜서 대부분의 “하나만 되는” 케이스를 놓쳤다. - 핵심 흐름 자체가 빠짐: 가장 오래 걸린 부분.
return !(downCount >= 2);라는 마지막 줄이, 위반이 1번이면 그게 실제로 고칠 수 있는지 전혀 확인하지 않고 무조건true를 반환하고 있었다.[3,4,2,3]처럼 위반은 1번인데 앞도 못 낮추고 뒤도 못 올리는 경우를 계속 놓쳤던 이유가 이거였다 — “위반이 1번이면 고칠 수 있는지 검사”하는 분기 자체가 없었다.
이 네 가지를 순서대로 고치고 나서야 통과했다. 특히 4번은 “AND/OR 방향은 맞게 고쳤는데 왜 여전히 틀리지?”라는 질문으로 이어졌는데, 답은 조건식의 문제가 아니라 애초에 그 조건식이 평가되는 지점(코드의 흐름) 자체가 잘못돼 있었다는 것이었다.
최종 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public boolean checkPossibility(int[] nums) {
if (nums.length == 1) {
return true;
}
int downCount = 0;
int idx = 0;
for (int i = 1; i < nums.length; i++) {
if (nums[i - 1] <= nums[i]) {
continue;
} else {
downCount++;
idx = i;
}
}
if (downCount >= 2) {
return false;
}
if (downCount == 1) {
boolean canLowerFront = idx <= 1 || nums[idx - 2] <= nums[idx];
boolean canRaiseBack = idx == nums.length - 1 || nums[idx + 1] >= nums[idx - 1];
return canLowerFront || canRaiseBack;
}
return true;
}
오늘 배운 내용
위반 횟수가 답의 전부가 아닌 문제가 있다. 1752, 1909까지는 “위반이 몇 번인가”만 세면 충분했지만, 이 문제는 위반이 1번이어도 그걸 “실제로 고칠 수 있는가”를 별도로 검증해야 한다. 그리고 그 검증은 배열을 다시 훑을 필요 없이, 위반 지점 양옆 딱 한 칸씩만 보면 된다 — 위반이 딱 한 곳뿐이라는 게 이미 보장됐으므로, 그 지점 앞뒤는 이미 정렬돼 있기 때문이다. “앞을 낮춘다”는 건 새 값이 nums[idx]와 같아지니 그쪽은 자동으로 맞고, 그 앞(nums[idx-2])과의 관계만 확인하면 된다. “뒤를 올린다”도 마찬가지로 반대쪽만 확인하면 된다.
오답노트
- 틀렸던 패턴 1: 방금
else로 들어와nums[i-1] > nums[i]가 확정된 지점에서, 조건문에 다시nums[i-1] <= nums[i]를 넣어 죽은 코드를 만듦. - 왜 틀렸나: 941에서 배운 “이 조건이 지금 이 시점에 실제로 참이 될 수 있는가”를 다시 확인하지 않고 조건을 만들었다.
- 틀렸던 패턴 2: “앞을 낮출 수 있는지” 확인할 때
idx-2대신idx-1과 비교. - 왜 틀렸나: “위반 지점”과 “그 지점보다 한 칸 더 앞”을 헷갈렸다.
- 틀렸던 패턴 3:
canLowerFront && canRaiseBack(둘 다 성립해야 고칠 수 있다고 판단). - 왜 틀렸나: 수정 기회가 하나뿐이라는 걸 코드에 반영하지 못했다 — 두 옵션 중 하나만 성공해도 충분한데, 둘 다 요구해버렸다.
- 틀렸던 패턴 4:
downCount==1일 때 고칠 수 있는지 검사하는 분기 자체가 없어서, 위반이 1번이면 무조건true를 반환. - 왜 틀렸나: “위반이 2번 이상이면 false, 아니면 true”라는 단순한 규칙에서 멈춰서, “위반이 정확히 1번일 때”라는 중간 케이스를 별도로 다뤄야 한다는 걸 놓쳤다.
- 다음에 떠올릴 시점: “위반/예외가 N번 이하면 괜찮다”는 규칙을 세울 때, “괜찮다”는 게 “아무 조건 없이 괜찮다”인지 “추가로 검증해야 괜찮다”인지 구분한다. 특히 “정확히 경계값(여기선 1번)”인 경우를 별도 분기로 다뤄야 하는지 항상 의심한다.
AI라면 어떻게 풀었을까
지금 코드는 먼저 전체를 훑어 위반 횟수와 마지막 위반 인덱스를 구한 다음, 그 결과로 판단하는 “2단계” 구조다. 이 문제는 위반을 만나는 순간 바로 수정을 시도하고, 그 수정이 실패하면 그 자리에서 바로 false를 반환하는 “1단계” 구조로도 풀 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean checkPossibility(int[] nums) {
int modified = 0;
for (int i = 1; i < nums.length; i++) {
if (nums[i - 1] <= nums[i]) {
continue;
}
if (modified == 1) {
return false;
}
modified++;
if (i - 2 >= 0 && nums[i - 2] > nums[i]) {
nums[i] = nums[i - 1];
} else {
nums[i - 1] = nums[i];
}
}
return true;
}
이 버전은 실제로 배열 값을 수정해가면서(nums[i] = nums[i-1] 또는 nums[i-1] = nums[i]) 진행한다 — 한 번 수정한 뒤에는 그다음 비교부터 그 수정된 값을 그대로 쓰기 때문에, “위반 지점을 기억해뒀다가 나중에 따로 검사”하는 과정 없이 흐름이 한 번에 끝난다. 다만 입력 배열 자체를 변경한다는 점(부작용)은 지금 코드(nums를 읽기만 하고 별도 변수로 판단)보다 조심해야 할 부분이다.