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

C++에서 곱이 주어진 값과 같은 두 연결 리스트의 쌍 개수 세기

문제 소개

두 개의 연결 리스트가 주어졌을 때, 각 리스트에 저장된 정수 요소들을 조합하여 만들 수 있는 모든 쌍 가운데 곱이 특정 값 k와 일치하는 쌍의 개수를 구하는 것이 이번 문제의 목표입니다. 연결 리스트(linked list)란 노드들이 포인터로 순차적으로 연결된 대표적인 선형 자료구조입니다.

입력 예시 1

vector<int> v_1 = {5, 7, 8, 10, 11};
vector<int> v_2 = {6, 4, 3, 2, 0};
int k = 20;

출력

곱이 주어진 값 k와 같은 두 연결 리스트의 쌍 개수: 2

풀이 과정

첫 번째 리스트의 각 원소와 두 번째 리스트의 각 원소를 짝지어 곱을 계산하면 다음과 같습니다.

(5, 6) = 30, (5, 4) = 20 ✓, (5, 3) = 15, (5, 2) = 10, (5, 0) = 0
(7, 6) = 42, (7, 4) = 28, (7, 3) = 21, (7, 2) = 14, (7, 0) = 0
(8, 6) = 48, (8, 4) = 32, (8, 3) = 24, (8, 2) = 16, (8, 0) = 0
(10, 6) = 60, (10, 4) = 40, (10, 3) = 30, (10, 2) = 20 ✓, (10, 0) = 0
(11, 6) = 66, (11, 4) = 44, (11, 3) = 33, (11, 2) = 22, (11, 0) = 0

총 25개의 쌍 중에서 (5, 4)와 (10, 2) 두 쌍만 곱이 20과 일치하므로, 정답은 2가 됩니다.

입력 예시 2

vector<int> v_1 = {2, 3, 5, 6};
vector<int> v_2 = {6, 4, 3};
int k = 9;

출력

곱이 주어진 값 k와 같은 두 연결 리스트의 쌍 개수: 1

풀이 과정

만들 수 있는 쌍은 (2, 6) = 12, (2, 4) = 8, (2, 3) = 6, (3, 6) = 18, (3, 4) = 12, (3, 3) = 9 ✓, (5, 6) = 30, (5, 4) = 20, (5, 3) = 15, (6, 6) = 36, (6, 4) = 24, (6, 3) = 18입니다. 이 중 곱이 9와 일치하는 쌍은 (3, 3) 하나뿐이므로 정답은 1입니다.

알고리즘 접근 방법

  • 입력 준비: 값 k와 정수형 데이터를 두 개의 벡터(vector)에 저장하고, 이 벡터들을 이용해 연결 리스트를 생성합니다.
  • 연결 리스트 생성 함수: 벡터를 인자로 받아 연결 리스트를 만드는 함수를 작성합니다.
    • 벡터의 크기만큼 반복하면서 ListNode 클래스 객체를 동적으로 생성합니다.
    • ptr->next가 NULL이 아닌 동안 ptr을 ptr->next로 이동시켜 리스트의 끝을 찾습니다.
    • 찾은 위치(ptr->next)에 벡터의 현재 값(vector[i])을 담은 새 노드를 연결합니다.
    • 리스트의 시작 노드(start)를 반환합니다.
  • 쌍 개수 계산 함수: 곱이 k와 일치하는 쌍의 개수를 반환하는 함수를 작성합니다.
    • 임시 변수 count를 0으로 초기화합니다.
    • 첫 번째 리스트를 가리키는 first_list와 두 번째 리스트를 가리키는 second_list 포인터를 선언합니다.
    • 외부 반복문으로 첫 번째 리스트를 처음부터 끝까지 순회합니다.
    • 내부 반복문으로 두 번째 리스트를 처음부터 끝까지 순회합니다.
    • 두 노드 데이터의 곱(first_list->data * second_list->data)이 k와 같으면 count를 1 증가시킵니다.
    • 모든 순회가 끝나면 count를 반환합니다.
  • 결과 출력: 최종 개수를 화면에 출력합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

class ListNode {
public:
    int data;
    ListNode *next;
    ListNode(int data){
        this->data = data;
        next = NULL;
    }
};

ListNode *CreateList(vector<int> v){
    ListNode *start = new ListNode(v[0]);
    for (int i = 1; i < v.size(); i++){
        ListNode *ptr = start;
        while (ptr->next != NULL){
            ptr = ptr->next;
        }
        ptr->next = new ListNode(v[i]);
    }
    return start;
}

int product_pair(ListNode *start_1, ListNode *start_2, int k){
    int count = 0;
    ListNode *first_list, *second_list;
    for (first_list = start_1; first_list != NULL; first_list = first_list->next){
        for (second_list = start_2; second_list != NULL; second_list = second_list->next){
            if ((first_list->data * second_list->data) == k){
                count++;
            }
        }
    }
    return count;
}

int main(){
    vector<int> v_1 = {5, 7, 8, 10, 11};
    ListNode* start_1 = CreateList(v_1);
    vector<int> v_2 = {6, 4, 3, 2, 0};
    ListNode* start_2 = CreateList(v_2);
    int k = 30;
    cout << "곱이 주어진 값 k와 같은 두 연결 리스트의 쌍 개수: "
         << product_pair(start_1, start_2, k);
    return 0;
}

실행 결과

위 코드를 컴파일하여 실행하면 다음과 같은 결과가 출력됩니다.

곱이 주어진 값 k와 같은 두 연결 리스트의 쌍 개수: 2

이 코드에서는 k를 30으로 설정했으며, (5 × 6) = 30과 (10 × 3) = 30 두 쌍이 조건을 만족하므로 결과는 2입니다.

복잡도 분석

두 연결 리스트의 길이를 각각 n과 m이라고 하면, 가능한 모든 쌍을 하나씩 검사해야 하므로 시간 복잡도는 O(n × m)입니다. 별도의 보조 자료구조 없이 포인터 몇 개만 활용하므로 공간 복잡도는 O(1)입니다.

마무리

이 문제는 이중 반복문을 활용한 완전 탐색(brute force) 방식의 기본적인 연결 리스트 순회 문제입니다. 리스트의 길이가 매우 길어지는 경우에는 해시 맵(hash map)을 이용해 한쪽 리스트의 값을 미리 저장해 두고 나머지 값을 빠르게 조회하는 방식으로 성능을 개선할 수 있습니다.