Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 정렬된 연결 리스트에서 중앙값(Median) 구하는 방법

이 문제에서는 N개의 요소로 이루어진 정렬된 연결 리스트(Sorted Linked List)가 주어지며, 우리의 과제는 이 리스트의 중앙값(Median)을 찾는 것입니다.

문제 개요

정렬된 연결 리스트란 모든 요소가 특정한 순서(오름차순 또는 내림차순)로 정렬되어 있는 단순 연결 리스트를 의미합니다.

예시: 4 -> 6 -> 7 -> 9 -> NULL

중앙값(Median)은 연결 리스트의 가운데에 위치한 요소를 말하며, 다음과 같이 정의할 수 있습니다.

  • N이 홀수인 경우: 중앙값은 (n/2)번째 요소입니다.
  • N이 짝수인 경우: 중앙값은 (n/2)번째 요소와 (n/2 + 1)번째 요소의 평균값입니다.

예제로 문제 이해하기

입력: 2 -> 3 -> 4 -> 6 -> 9 -> NULL
출력: 4

위 예제에서 리스트의 길이 N은 5(홀수)이므로, 가운데에 있는 세 번째 요소인 4가 중앙값이 됩니다.

해결 접근 방법 1: 순회 후 카운트 기반 탐색

가장 단순한 해결 방법은 연결 리스트를 한 번 순회하면서 전체 요소의 개수를 세는 것입니다.

  1. 개수가 홀수라면, 리스트를 다시 순회하여 N/2번째 요소를 찾아 반환합니다.
  2. 개수가 짝수라면, N/2번째 요소와 (N/2 + 1)번째 요소를 찾아 두 값을 더한 뒤 2로 나누어 평균을 계산합니다.

이 방법은 직관적이지만, 리스트를 두 번 순회해야 하므로 시간 복잡도 측면에서 비효율적일 수 있습니다.

해결 접근 방법 2: 투 포인터(Two Pointer) 기법

더 효율적인 대안은 두 개의 포인터를 사용해 리스트를 한 번만 순회하면서 중앙값을 찾는 방법입니다. 요소의 개수를 미리 셀 필요가 없다는 것이 핵심 장점입니다.

여기서는 pointer1(느린 포인터)과 pointer2(빠른 포인터) 두 개의 포인터를 사용합니다. 빠른 포인터는 한 번에 두 칸씩 이동하고, 느린 포인터는 한 칸씩 이동합니다. 빠른 포인터가 리스트 끝에 도달하면, 느린 포인터는 자연스럽게 중앙에 위치하게 됩니다.

종료 조건에 따라 결과를 판단할 수 있습니다.

  • pointer2가 NULL이 아닌 경우(리스트 길이가 홀수): pointer1이 가리키는 값이 중앙값입니다.
  • pointer2가 NULL인 경우(리스트 길이가 짝수): pointer1의 이전 노드(prev)와 pointer1 데이터의 평균값이 중앙값입니다.

C++ 구현 예제

다음은 위에서 설명한 투 포인터 알고리즘의 동작을 보여주는 프로그램입니다.

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    struct Node* next;
};
void findMedianValue(Node* head){
    Node* ptr1 = head;
    Node* ptr2 = head;
    Node* prev = head;
    if (head != NULL) {
        while (ptr2 != NULL && ptr2->next != NULL) {
            ptr2 = ptr2->next->next;
            prev = ptr1;
            ptr1 = ptr1->next;
        }
        if (ptr2 != NULL)
            cout<<ptr1->data;
        else
            cout<<float(ptr1->data + prev->data) / 2;
    }
}
void pushVal(struct Node** head_ref, int new_data){
    Node* new_node = new Node;
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}
int main(){
   struct Node* head = NULL;
   pushVal(&head, 3);
   pushVal(&head, 5);
   pushVal(&head, 6);
   pushVal(&head, 8);
   pushVal(&head, 9);
   pushVal(&head, 11);
   cout<<"연결 리스트의 중앙값은 ";
   findMedianValue(head);
   return 0;
}

실행 결과

연결 리스트의 중앙값은 7

코드 설명 및 시간 복잡도

위 코드에서 pushVal 함수는 새 노드를 리스트 맨 앞에 삽입하므로, 실제 리스트는 11 -> 9 -> 8 -> 6 -> 5 -> 3 순으로 구성됩니다. 이 리스트의 길이는 6(짝수)이며, 가운데 두 요소인 8과 6의 평균인 7이 중앙값으로 출력됩니다.

  • 시간 복잡도: O(N) — 리스트를 한 번만 순회합니다.
  • 공간 복잡도: O(1) — 추가 메모리 없이 포인터만 사용합니다.

투 포인터 기법을 활용하면 리스트의 길이를 미리 알 필요 없이 단일 순회만으로 중앙값을 효율적으로 구할 수 있습니다.