n개의 요소를 가진 배열 A가 주어졌을 때, 이 배열이 쌍 단위로 정렬(pairwise sorted)되어 있는지 확인해야 합니다. 예를 들어 배열이 {8, 10, 18, 20, 5, 15}라고 가정해 보겠습니다. 각 쌍인 (8, 10), (18, 20), (5, 15)가 모두 오름차순으로 정렬되어 있으므로, 이 배열은 쌍 단위로 정렬된 것입니다. 만약 배열의 요소 개수가 홀수라면 마지막 요소는 짝이 없으므로 검사에서 제외됩니다.
접근 방법
접근 방식은 매우 간단합니다. 인덱스 i를 0부터 시작하여 2씩 증가시키면서 다음을 반복합니다.
- i번째 요소가 i+1번째 요소보다 크면 해당 쌍은 정렬되어 있지 않으므로 false를 반환합니다.
- 모든 쌍에 대해 검사를 통과하면 true를 반환합니다.
배열 전체를 한 번만 순회하며 인접한 두 요소씩 비교하므로 시간 복잡도는 O(n)이며, 추가 메모리 없이 제자리에서 검사할 수 있습니다.
구현 예제
#include <iostream>
using namespace std;
bool isPairwiseSorted(int arr[], int n) {
if(n <= 1)
return true;
// 마지막 인덱스까지 접근하지 않도록 n-1까지만 반복
for(int i = 0; i < n - 1; i += 2){
if(arr[i] > arr[i + 1])
return false;
}
return true;
}
int main() {
int arr[] = {8, 10, 18, 20, 5, 15};
int n = sizeof(arr)/sizeof(arr[0]);
if(isPairwiseSorted(arr, n)){
cout << "이 배열은 쌍 단위로 정렬되어 있습니다";
} else {
cout << "이 배열은 쌍 단위로 정렬되어 있지 않습니다";
}
return 0;
}실행 결과
이 배열은 쌍 단위로 정렬되어 있습니다
위 코드에서 반복 조건을 i < n - 1로 설정한 점에 유의하세요. 이렇게 하면 배열 길이가 홀수일 때 마지막 요소가 자동으로 무시되고, 범위를 벗어난 배열 접근(out-of-bounds access)도 방지할 수 있습니다. 요소가 1개 이하인 배열은 항상 정렬된 것으로 간주하여 true를 반환합니다.