C++에서 연결 리스트가 쌍별로 정렬되어 있는지 확인하는 방법

문제 개요

n개의 요소를 가진 연결 리스트 L이 주어졌을 때, 이 리스트가 쌍별(pairwise)로 정렬되어 있는지 확인해야 합니다. 예를 들어 리스트가 {8, 10, 18, 20, 5, 15}라고 하면, (8, 10), (18, 20), (5, 15)의 각 쌍이 모두 정렬되어 있으므로 이 리스트는 쌍별로 정렬된 것입니다.

리스트의 요소 개수가 홀수인 경우에는 마지막에 짝이 없어 남는 하나의 요소를 검사 대상에서 제외합니다.

접근 방식

풀이 방법은 매우 간단합니다. 리스트를 왼쪽에서 오른쪽으로 한 번 순회하면서 인접한 두 요소씩 짝을 지어 각 쌍이 정렬되어 있는지 확인합니다. 정렬되지 않은 쌍이 하나라도 발견되면 즉시 false를 반환하고, 모든 쌍이 정렬되어 있다면 true를 반환합니다.

참고로 아래 코드의 append() 함수는 새 노드를 리스트의 맨 앞(헤드)에 추가하기 때문에 노드가 입력 배열의 역순으로 저장됩니다. 따라서 isPairwiseSorted() 함수는 저장된 리스트에서 각 쌍의 앞 요소가 뒤 요소보다 크거나 같은지, 즉 쌍 단위로 내림차순인지 검사하며, 이는 원래 배열 기준으로 각 쌍이 오름차순인지 확인하는 것과 동일한 결과를 줍니다.

예제 코드

#include <iostream>
#include <cmath>
using namespace std;
class Node{
    public:
    int data;
    Node *next;
};
void append(struct Node** start, int key) {
    Node* new_node = new Node;
    new_node->data = key;
    new_node->next = (*start);
    (*start) = new_node;
}
bool isPairwiseSorted(Node *start) {
    bool flag = true;
    struct Node* temp = start;
    while (temp != NULL && temp->next != NULL) {
        if (temp->data < temp->next->data) {
            flag = false;
            break;
        }
        temp = temp->next->next;
    }
    return flag;
}
int main() {
    Node *start = NULL;
    int arr[] = {8, 10, 18, 20, 5, 15};
    int n = sizeof(arr)/sizeof(arr[0]);
    for(int i = 0; i<n; i++){
        append(&start, arr[i]);
    }
    if(isPairwiseSorted(start)){
        cout << "This is pairwise sorted";
    } else {
        cout << "This is not pairwise sorted";
    }
}

출력

This is pairwise sorted

복잡도 분석

리스트 전체를 한 번만 순회하면 되므로 시간 복잡도는 O(n)이며, 별도의 추가 메모리 없이 O(1)의 공간 복잡도로 문제를 해결할 수 있습니다.