두 개의 연결 리스트가 주어졌을 때, 각 리스트의 정수 요소로 만들 수 있는 쌍(pair) 중 그 합이 주어진 값(예: k)과 같아지는 쌍의 개수를 구하는 것이 이 글의 목표입니다. 연결 리스트는 링크를 통해 서로 연결된 데이터 구조들의 나열을 의미합니다.
예제 1
입력
vector v_1 = {5, 7, 8, 10, 11}
vector v_2 = {6, 4, 3, 2, 0}, int k = 11출력
합이 주어진 값 k와 같은 두 연결 리스트의 쌍 개수: 4
설명
주어진 연결 리스트로 만들 수 있는 모든 조합 중 합이 11(k)이 되는 쌍은 (5, 6), (7, 4), (8, 3), (11, 0)으로 총 4개입니다. 예를 들어 (5, 4) = 9, (7, 6) = 13, (10, 2) = 12처럼 나머지 조합들은 합이 11이 아니므로 개수에 포함되지 않습니다.
예제 2
입력
vector v_1 = {2, 3, 5, 6}
vector v_2 = {6, 4, 3}, int k = 6출력
합이 주어진 값 k와 같은 두 연결 리스트의 쌍 개수: 2
설명
만들 수 있는 쌍 중 합이 6(k)이 되는 것은 (2, 4)와 (3, 3) 두 가지뿐입니다. (2, 6) = 8, (5, 6) = 11 등 나머지 조합은 조건을 만족하지 않으므로 최종 결과는 2가 됩니다.
프로그램에서 사용하는 접근 방식
k 값과 정수형 데이터를 두 개의 벡터에 입력받고, 이 벡터들을 전달하여 연결 리스트를 생성합니다.
벡터를 인자로 받아 연결 리스트를 만드는 함수를 작성합니다.
벡터의 크기만큼 반복하면서 ListNode 클래스의 포인터 객체를 생성합니다.
ptr->next가 NULL이 아닌 동안 ptr을 ptr->next로 이동시킵니다.
ptr->next에 vector[i] 값을 저장합니다.
리스트의 시작점인 start 포인터를 반환합니다.
주어진 합과 일치하는 쌍의 개수를 반환하는 함수를 작성합니다.
임시 변수 count를 선언하고 0으로 초기화합니다.
첫 번째 리스트를 가리키는 *first_list와 두 번째 리스트를 가리키는 *second_list 두 개의 포인터 객체를 생성합니다.
첫 번째 리스트의 시작 포인터부터 리스트가 끝날 때까지 외부 루프를 실행합니다.
루프 내부에서 두 번째 리스트의 시작 포인터부터 리스트가 끝날 때까지 내부 루프를 실행합니다.
루프 안에서 IF (first_list->data + second_list->data) == k 조건을 검사하고, 참이면 count를 1 증가시킵니다.
최종적으로 count를 반환합니다.
결과를 출력합니다.
이 방법은 두 리스트의 모든 조합을 비교하는 브루트포스 방식으로, 시간 복잡도는 첫 번째 리스트의 길이를 n, 두 번째 리스트의 길이를 m이라 할 때 O(n × m)입니다.
예제 코드
#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 sum_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 = 11;
cout<<"Count of pairs from two linked lists whose sum is equal to a given value k are: "<<sum_pair(start_1, start_2, k);
}
출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Count of pairs from two linked lists whose sum is equal to a given value k are: 4