[LeetCode-1752] 배열 끝에서 처음으로 넘어가는 지점(wraparound)도 똑같은 규칙으로
- 문제 링크: https://leetcode.com/problems/check-if-array-is-sorted-and-rotated/
- 파일 경로:
src/main/java/coding_test/배열_리스트/LC1752_CheckIfArrayIsSortedAndRotated.java - 난이도: Easy
문제 설명
정수 배열 nums가 주어진다. 이 배열이 “원래 비내림차순으로 정렬돼 있던 배열을 몇 칸 회전시킨 것”이면(0칸 회전도 포함) true, 아니면 false를 반환한다.
1
2
3
4
5
Input: nums = [3,4,5,1,2]
Output: true // [1,2,3,4,5]를 3칸 회전시킨 것
Input: nums = [2,1,3,4]
Output: false
시행착오
가장 먼저 시도한 건 배열을 문자열로 바꿔서 이어붙이고 비교하는 방식이었다. 정렬한 배열과 원본 배열을 각각 문자열로 만든 다음, 원본 문자열을 이런저런 방식으로 잘라 붙여서 정렬된 문자열과 일치하는지 찾으려고 했는데, 스스로 “이건 아닌 것 같다”고 느껴서 포기했다. 문자열 변환은 이 문제에 필요 없는 우회로였다.
두 번째 시도는 941(Valid Mountain Array)에서 썼던 up/down 상태 플래그를 그대로 가져온 것이었다. 그런데 이 문제는 “오르막 하나, 내리막 하나”인 산 모양이 아니라, “거의 끝까지 계속 오르다가 딱 한 지점에서만 뚝 떨어지는” 모양이라 완전히 다른 구조였다. [2,1,3,4]처럼 실제로는 무효인 배열도 이 상태 모델로는 true가 나와버렸다 — 오르막/내리막을 번갈아 추적하는 방식 자체가 “몇 번 내려갔는가”를 정확히 세지 못했기 때문이다.
결국 접근을 단순화했다. “정렬된 배열을 한 곳만 잘라 회전시킨 것”이라면, 원본 배열을 순회했을 때 nums[i] > nums[i+1](내려가는 지점)이 최대 한 번만 나올 수 있다. 그래서 상태 플래그 없이, 내려가는 지점의 개수(downCount)만 세는 방식으로 바꿨다.
여기서 또 한 번 헤맸다 — 배열 끝에서 첫 원소로 돌아가는 지점(마지막→처음, wraparound)을 빠뜨렸다. 처음엔 이 지점을 빼먹었고([2,1,3,4]에서 실패), 그다음엔 이 지점만 특별 취급해서 return false를 바로 반환하는 코드를 넣었다가([3,4,5,1,2]에서 실패 — 이 지점이 유일한 위반일 수도 있는데 무조건 실패 처리해버렸다), 그다음엔 부등호 방향을 반대로 써서 또 틀렸다. 결국 “wraparound도 메인 루프와 완전히 같은 규칙(nums[last] > nums[0]이면 카운트 증가)”으로 통일하고 나서야 통과했다.
최종 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public boolean check(int[] nums) {
if (nums.length == 0 || nums.length == 1) {
return true;
}
int downCount = 0;
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] > nums[i + 1]) {
downCount++;
}
if (i == nums.length - 2) {
if (nums[nums.length - 1] > nums[0]) {
downCount++;
}
}
}
if (downCount == 0) {
return true;
}
return downCount <= 1;
}
오늘 배운 내용
문제의 모양을 먼저 정확히 파악하지 않으면, 이전 문제에서 잘 먹혔던 모델을 잘못 재사용하게 된다. 941의 “산 모양(오르막 1번, 내리막 1번)”과 1752의 “회전된 정렬 배열(거의 다 오르막, 예외 지점 최대 1번)”은 겉보기엔 둘 다 “상태가 바뀌는 지점을 센다”는 점에서 비슷해 보이지만 실제로는 다른 구조다. 그리고 배열을 “회전”으로 다루는 문제에서는 마지막 원소와 첫 원소를 잇는 지점(wraparound)을 별도 규칙이 아니라, 메인 로직과 똑같은 규칙으로 처리하는 게 안전하다 — 특별 취급하려다가 오히려 버그가 늘었다.
오답노트
- 틀렸던 패턴 1: 문자열로 변환해서 비교하는 접근. 왜 틀렸나: 이 문제는 배열 원소 간 대소 비교만으로 충분한데, 문자열 변환은 불필요한 복잡도를 더했다.
- 틀렸던 패턴 2: 941의
up/down상태 모델을 그대로 재사용. 왜 틀렸나: 이 문제는 “오르막→내리막” 산 모양이 아니라 “거의 오르막, 예외 1번”인 회전 모양이라 상태 전환을 세는 방식 자체가 안 맞았다. - 틀렸던 패턴 3: wraparound 검사에서
return false를 즉시 반환. 왜 틀렸나: 이 지점이 유일한 위반일 수도 있는데, 다른 위반들과 다르게 취급해서 정상 케이스까지 실패시켰다. - 틀렸던 패턴 4: wraparound 비교 부등호 방향이 반대(
<를 써야 할 자리에 실수, 혹은 그 반대). 왜 틀렸나: 메인 루프의 규칙(nums[i] > nums[i+1])을 그대로 옮기지 않고 새로 만들다가 방향을 헷갈렸다. - 고친 패턴: wraparound도 메인 루프와 똑같이
nums[last] > nums[0]이면downCount++, 특별 취급 없음. - 다음에 떠올릴 시점: 배열을 순환(회전)으로 다루는 문제를 보면, “끝에서 처음으로 넘어가는 지점”을 메인 로직과 다른 규칙으로 짜고 싶어질 때마다 “정말 다른 규칙이 필요한가, 아니면 그냥 같은 조건을 한 번 더 적용하면 되는가”부터 확인한다.
AI라면 어떻게 풀었을까
세션 중에 실제로 제안했던 방식인데, wraparound를 메인 루프 밖에서 따로 처리하는 대신 나머지 연산자(%)로 인덱스를 순환시키면 분기 자체가 필요 없어진다.
1
2
3
4
5
6
7
8
9
10
public boolean check(int[] nums) {
int n = nums.length;
int drops = 0;
for (int i = 0; i < n; i++) {
if (nums[i] > nums[(i + 1) % n]) {
drops++;
}
}
return drops <= 1;
}
i가 마지막 인덱스일 때 (i + 1) % n이 자동으로 0이 되기 때문에, i == nums.length - 2처럼 wraparound 지점을 따로 찾아서 예외 처리할 필요가 없다. 오늘 겪었던 시행착오(wraparound에서 return false를 잘못 넣었다가, 부등호 방향을 반대로 썼다가 하는 것)가 전부 “메인 루프와 다른 규칙을 wraparound에 새로 만들려는 시도”에서 나왔는데, % 연산자로 순환시키면 애초에 “다른 규칙”을 만들 여지 자체가 없어진다.