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

C++ 정렬된 이중 연결 리스트에서 곱이 주어진 값과 같은 쌍 찾기

개념

양의 서로 다른 정수로 구성되어 오름차순으로 정렬된 이중 연결 리스트(Doubly Linked List)가 주어졌을 때, 두 노드 데이터의 곱이 주어진 값 x와 같아지는 모든 쌍(pair)을 추가 공간을 사용하지 않고 찾아내는 것이 이 문제의 목표입니다.

입력 / 출력 예시

예시 1

List = 1 <=> 2 <=> 4 <=> 5 <=> 6 <=> 8 <=> 9
x = 8

출력:

(1, 8), (2, 4)

예시 2

List = 1 <=> 2 <=> 3 <=> 4 <=> 5 <=> 6 <=> 7
x = 6

출력:

(1, 6), (2, 3)

해결 방법

단순한 접근법(Simple Approach): 두 개의 중첩 반복문을 사용해 연결 리스트를 순회하면서 가능한 모든 쌍을 검사하고, 그 곱이 x와 같은지 확인하는 방식입니다. 이 경우 시간 복잡도는 O(n²)이 되며, 여기서 n은 이중 연결 리스트의 전체 노드 수입니다.

효율적인 해결법(Efficient Solution): 정렬된 배열에서 자주 사용되는 두 포인터(Two Pointer) 기법을 이중 연결 리스트에 적용하면 O(n) 시간 안에 문제를 해결할 수 있습니다. 알고리즘의 단계는 다음과 같습니다.

  1. 정렬된 이중 연결 리스트에서 후보 원소를 가리키기 위해 두 개의 포인터 변수를 초기화합니다.
  2. first 포인터는 리스트의 시작 노드(first = head)로, second 포인터는 리스트의 마지막 노드(second = last_node)로 초기화합니다.
  3. 연결 리스트는 임의 접근(random access)이 불가능하므로, second 포인터를 얻기 위해 먼저 리스트 끝까지 순회해야 합니다.
  4. 두 포인터가 가리키는 값의 곱이 x보다 작으면 first 포인터를 앞쪽(다음 노드)으로 이동하고, 곱이 x보다 크면 second 포인터를 뒤쪽(이전 노드)으로 이동합니다.
  5. 반복문의 종료 조건도 배열과 다릅니다. 두 포인터 중 하나가 NULL이 되거나, 서로 교차하거나(second->next = first), 두 포인터가 같아지면(first == second) 반복문을 종료합니다.

C++ 구현 예제

// 정렬된 이중 연결 리스트에서
// 주어진 곱 x를 갖는 쌍을 찾는 C++ 프로그램
#include <bits/stdc++.h>
using namespace std;

// 이중 연결 리스트의 노드 구조체
struct Node1 {
    int data1;
    struct Node1 *next1, *prev1;
};

// 곱이 주어진 값 x와 같은 쌍을 찾는 함수
void pairProduct(struct Node1* head1, int x1){
    // 두 포인터 설정:
    // first는 DLL의 시작을, second는 DLL의 끝을 가리킴
    struct Node1* first1 = head1;
    struct Node1* second1 = head1;
    while (second1->next1 != NULL)
        second1 = second1->next1;

    // 쌍을 찾았는지 여부를 추적하는 플래그
    bool found1 = false;

    // 두 포인터 중 하나가 NULL이 되거나,
    // 서로 교차하거나(second1->next1 == first1),
    // 같아지면(first1 == second1) 반복문 종료
    while (first1 != NULL && second1 != NULL && first1 != second1 && second1->next1 != first1) {
        // 쌍을 찾은 경우
        if ((first1->data1 * second1->data1) == x1) {
            found1 = true;
            cout << "(" << first1->data1 << ", " << second1->data1 << ")" << endl;
            // first 포인터를 앞쪽으로 이동
            first1 = first1->next1;
            // second 포인터를 뒤쪽으로 이동
            second1 = second1->prev1;
        } else {
            if ((first1->data1 * second1->data1) < x1)
                first1 = first1->next1;
            else
                second1 = second1->prev1;
        }
    }

    // 쌍이 존재하지 않는 경우
    if (found1 == false)
        cout << "No pair found";
}

// 이중 연결 리스트 맨 앞에 새 노드를 삽입하는 유틸리티 함수
void insert(struct Node1** head1, int data1){
    struct Node1* temp1 = new Node1;
    temp1->data1 = data1;
    temp1->next1 = temp1->prev1 = NULL;
    if (!(*head1))
        (*head1) = temp1;
    else {
        temp1->next1 = *head1;
        (*head1)->prev1 = temp1;
        (*head1) = temp1;
    }
}

// 드라이버 코드
int main(){
    // 이중 연결 리스트 생성
    struct Node1* head1 = NULL;
    insert(&head1, 7);
    insert(&head1, 6);
    insert(&head1, 5);
    insert(&head1, 4);
    insert(&head1, 3);
    insert(&head1, 2);
    insert(&head1, 1);
    int x1 = 6;
    pairProduct(head1, x1);
    return 0;
}

실행 결과

(1, 6)
(2, 3)

복잡도 분석

시간 복잡도: O(n) — 두 포인터가 리스트의 양 끝에서 시작해 서로를 향해 한 번씩만 이동하므로 전체 노드를 최대 한 번 순회합니다.

공간 복잡도: O(1) — 포인터 두 개와 플래그 변수 외에 추가 메모리를 사용하지 않습니다.