Check if an Array Is Sorted
정수 배열 nums가 주어집니다. 배열이 비내림차순, 즉 모든 요소가 다음 요소보다 작거나 같으면 true를 반환하고, 그렇지 않으면 false를 반환하세요. 이웃한 요소가 같아도 괜찮습니다. [2, 2, 3]은 정렬된 것으로 간주합니다. 요소가 하나인 배열은 정렬된 배열입니다.
함수
- numsinteger-array
- 확인할 정수 배열
- 반환값boolean
- 모든 요소가 다음 요소보다 작거나 같으면 true, 그렇지 않으면 false
제약 조건
1 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109
예제
- 입력
- nums = [1, 3, 3, 7]
- 출력
- true
- 설명
- 각 단계는 올라가거나 같은 수준을 유지합니다: 1에서 3으로, 3에서 3으로, 3에서 7로. 3이 반복되어도 허용되므로 답은
true입니다.
- 입력
- nums = [2, 5, 4, 9]
- 출력
- false
- 설명
- 5에서 4로 가는 단계는 내려갑니다. 끝에 있는 9가 가장 큰 값이더라도 이러한 단계 하나만으로 배열은 정렬되지 않은 상태가 되므로, 답은
false입니다.
제출 시 숨은 테스트 +16개
후속 질문
증가하는 방향이나 감소하는 방향으로 정렬되어 있을 수 있는 배열을 한 번의 순회로 확인하려면 어떻게 해야 할까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
배열이 정렬되어 있지 않다면, 배열의 어느 부분에서 그 사실을 확인할 수 있나요? 서로 멀리 떨어진 요소들을 비교해야 하나요?
각 요소를 바로 다음 요소와 비교하는 것으로 충분합니다. 같은 이웃 요소가 있어도 괜찮으며, 순서가 깨지는 것은 값이 낮아지는 경우뿐입니다.
인접한 쌍을 반복해서 확인하고, 왼쪽 값이 오른쪽 값보다 큰 첫 번째 쌍에서
false를 반환하세요. 그러한 쌍이 없으면true를 반환하세요.
풀이
배열은 어떤 요소도 바로 뒤에 오는 요소보다 크지 않을 때 정렬된 것입니다. 서로 멀리 떨어진 요소를 비교할 필요는 없습니다. 모든 인접한 쌍이 순서대로라면 배열 전체가 정렬된 것입니다. 따라서 n-1개의 쌍을 한 번 순회하면서 처음으로 순서가 어긋나는 지점에서 멈추면 됩니다.
복사본을 정렬하고 비교하기
핵심 아이디어
정렬된 배열은 정렬해도 바뀌지 않는 배열입니다. 따라서 nums의 복사본을 만들고, 복사본을 정렬한 다음 원본과 위치별로 일치하는지 확인하세요. 모든 위치가 일치하면 nums는 이미 정렬된 상태였습니다.
[2, 5, 4, 9]의 경우 정렬된 복사본은 [2, 4, 5, 9]입니다. 위치 1에는 원본에서 5가, 복사본에서 4가 있으므로 답은 false입니다. [1, 3, 3, 7]의 경우 복사본은 원본과 같으므로 답은 true입니다.
이 방법은 올바르지만, 문제에서 요구하는 것보다 더 많은 작업을 합니다. 정렬에는 O(n log n)의 비용이 들며, 숫자 5000개를 정렬할 때 비교 횟수는 약 6 × 10^4회입니다. 복사본에는 O(n)의 메모리가 필요합니다. 또한 첫 번째 쌍부터 순서가 어긋나더라도 항상 배열 전체를 읽습니다.
알고리즘
- 원본이 변경되지 않도록
nums를 복사합니다. - 복사본을 숫자의 오름차순으로 정렬합니다.
- 복사본과
nums를 각 위치별로 비교합니다. - 모든 위치가 일치하면
true를 반환하고, 그렇지 않으면false를 반환합니다.
def isSorted(nums):
# sorted returns a new list, so nums itself is left as it was.
return sorted(nums) == nums각 이웃 쌍을 비교합니다
핵심 아이디어
배열이 정렬되어 있는지 확인하기 위해 정렬된 버전이 필요한 것은 아닙니다. 각 요소가 바로 다음 요소보다 작거나 같을 때 배열은 정확히 비내림차순입니다. ≤는 연쇄적으로 적용되므로(a ≤ b와 b ≤ c이면 a ≤ c), 이웃한 n-1개의 쌍을 확인하면 모든 위치 쌍을 확인하는 셈입니다.
i를 1부터 n-1까지 순회하며 nums[i-1]와 nums[i]를 비교합니다. [2, 5, 4, 9]의 경우 (2, 5) 쌍은 문제가 없지만 (5, 4) 쌍은 값이 작아지므로, 9를 확인하지 않고 바로 false를 반환합니다. 같은 값인 이웃 요소는 통과합니다. >일 때만 실패하기 때문입니다.
각 쌍을 한 번씩만 비교하므로 시간 복잡도는 O(n)이고, 루프 인덱스만 추가 메모리로 사용하므로 공간 복잡도는 O(1)입니다. 두 값을 빼지 말고 직접 비교하세요. 값이 10^9까지 가능하므로 차이가 32비트 정수의 범위를 초과할 수 있습니다.
알고리즘
i를 1부터n-1까지 반복합니다.nums[i-1] > nums[i]이면false를 반환합니다.- 반복문이 끝나면
true를 반환합니다. 요소가 하나뿐이면 반복문을 건너뛰며, 정렬된 상태입니다.
def isSorted(nums):
for i in range(1, len(nums)):
# One step down anywhere breaks the order.
if nums[i - 1] > nums[i]:
return False
return True
함정과 경계 사례
루프는 짧기 때문에 버그는 양 끝부분과 비교에 있습니다.
- 같은 값인 이웃을 실패로 처리하기.
nums[i-1] >= nums[i]를 검사하면[1, 3, 3, 7]을 거부합니다. 엄격한 내림(>)만 순서를 깨뜨립니다. - 끝을 넘어 읽기.
0부터n-1까지 도는 루프에서nums[i]와nums[i+1]을 비교한다면, 배열 범위 밖을 읽지 않도록 한 칸 일찍 멈춰야 합니다.i = 1에서 시작해i-1과 비교하면 이 문제를 피할 수 있습니다. - 비교 대신 빼기.
nums[i] - nums[i-1] >= 0은 같아 보이지만,10^9 - (-10^9) = 2 × 10^9는 32비트 int의 범위를 벗어나 음수로 오버플로되므로[-1000000000, 1000000000]을 정렬되지 않은 것으로 판정합니다.x - y로 작성한 qsort 비교 함수에서도 같은 오버플로가 발생합니다. - 숫자를 텍스트로 정렬하기. JavaScript에서 비교 함수 없이
sort()를 호출하면10이9보다 앞에 오므로, 정렬 후 비교하는 검사는 잘못된 결과를 냅니다.
자주 묻는 질문4
배열이 정렬되어 있는지 어떻게 확인하나요?
각 요소를 다음 요소와 비교하세요. 어떤 요소든 오른쪽 이웃보다 크면 배열은 정렬되지 않은 것이므로 중단할 수 있습니다. 그런 요소를 찾지 못한 채 끝에 도달하면 배열은 정렬된 것입니다. 이 작업에는 O(n) 시간이 걸리고 추가 공간은 O(1)이 필요합니다.
이웃을 확인하는 것만으로 충분한 이유는 무엇인가요?
순서 관계는 연쇄적입니다. 즉, a ≤ b이고 b ≤ c이면 a ≤ c입니다. 따라서 인접한 모든 쌍이 순서대로 되어 있으면 모든 위치 쌍도 순서대로 되어 있습니다. 반대로 정렬되지 않은 배열에는 값이 감소하는 인접한 쌍이 적어도 하나 있습니다.
모든 요소가 같은 배열은 정렬된 상태인가요?
비감소 순서라면 맞습니다. [4, 4, 4]는 어떤 요소도 다음 요소보다 크지 않으므로 정렬된 상태입니다. 문제에서 대신 엄격한 오름차순을 요구한다면, 같은 이웃 요소도 거부하도록 검사를 변경하세요.
복사본을 정렬한 다음 원본과 비교해도 되나요?
네, 올바른 답을 제공하지만 복사본을 만드는 데 O(n log n)의 시간과 O(n)의 추가 메모리가 듭니다. 이웃 항목 검사는 더 빠르고 복사본이 필요 없으며, 나머지를 읽지 않고도 첫 번째 하강 지점에서 반환할 수 있습니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def isSorted(nums):
# 여기에 코드를 작성하세요케이스 1
케이스 2
입력
nums = [1, 3, 3, 7]
기대값
true