2๊ฐ์ ๋ฆฌ์คํธ ํฉ์น๊ธฐ
EDWITH CS50 ๊ฐ์ข๋ฅผ ๋ชจ๋ ์๊ฐํ ์ฌ๋ฌ๋ถ์ ์ ๋ฅํ ๊ฐ๋ฐ์๋ก ํ์ฌ์ ์๋ฌธ์ด๋ ํต์ฌ ๋ถ์๋ก ๋ฐฐ์น๋์์ต๋๋ค. ํต์ฌ๋ถ์์ ์ฃผ์ ์๋ฌด ์ค ํ๋๋ ๋ค๋ฅธ ๋ถ์์ ์ ๋ฌด๋ฅผ ์ข ํฉํ๋ ์ผ์ ๋๋ค. ๋ถ์ ๋ฐฐ์น ์ฒซ ์ ๋ฌด๋ก A๋ถ์์์ ์ํํ ์ ๋ฌด์ B๋ถ์์์ ์ํํ ์ ๋ฌด๋ฅผ ํฉ์น๋ ์ผ์ ๋งก๊ฒ ๋์์ต๋๋ค.
A๋ถ์์์๋ ๋ฏธ๊ตญ ์ง์ฌ๋ค์ ๋งค์ถ์ด ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ๋ ์๋ฃ๋ฅผ ์ฐ๊ฒฐ๋ฆฌ์คํธ ํํ๋ก ๋ณด๋ด์๊ณ , B๋ถ์์์๋ ํ๊ตญ ์ง์ฌ๋ค์ ๋งค์ถ์ด ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ๋ ์๋ฃ๋ฅผ ์ฐ๊ฒฐ๋ฆฌ์คํธ ํํ๋ก ๋ณด๋ด์์ต๋๋ค.
์ฌ๋ฌ๋ถ์ ์ ๋ฌด๋ ์ด์ ๋ ์ฐ๊ฒฐ๋ฆฌ์คํธ๋ฅผ ํ๋์ ์ฐ๊ฒฐ๋ฆฌ์คํธ๋ก ํฉ์น์ด ํ๊ตญ๊ณผ ๋ฏธ๊ตญ ์ง์ฌ๋ค์ ๋งค์ถ์ด ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ๋ ์ฐ๊ฒฐ๋ฆฌ์คํธ๋ฅผ ๋ง๋์๋ ๊ฒ์ ๋๋ค. ์๋ฅผ ๋ค์ด, A๋ถ์์์ ๋ณด๋ด์จ ์ฐ๊ฒฐ๋ฆฌ์คํธ๊ฐ 2->6->9->10, B๋ถ์์์ ๋ณด๋ด์จ ์ฐ๊ฒฐ๋ฆฌ์คํธ๊ฐ 1->5->7->8->11 ์ด๋ผ๋ฉด ์ฌ๋ฌ๋ถ์ด ๋ง๋ค ์ฐ๊ฒฐ๋ฆฌ์คํธ๋ 1->2->5->6->7->8->9->10->11 ์ด ๋์ด์ผ ํฉ๋๋ค.
์ ๋ฌด ์ํ์ ์ํด ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ฅผ ํฉ์น๋ ํจ์์ ํฉ์ณ์ง ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ฅผ ์ถ๋ ฅํ๋ ํจ์๋ฅผ ๋ง๋ค์ด์ฃผ์ธ์.
/**
* ์ฐ๊ฒฐ ๋ฆฌ์คํธ์ ํํ๋ ์๋์ ๊ฐ์ต๋๋ค.
* struct ListNode {
* int sales;
* struct ListNode *next;
* } ListNode;
*/
struct ListNode* mergeTwoLists(ListNode* list1, ListNode* list2){
// ํจ์๋ฅผ ์ฑ์์ฃผ์ธ์!
}
void append(ListNode* l, int data) {
// ํจ์๋ฅผ ์ฑ์์ฃผ์ธ์.
void printMergedLinkedList(ListNode* list3) {
// ํจ์๋ฅผ ์ฑ์์ฃผ์ธ์!
}
int main() {
ListNode* listA = (ListNode*)malloc(sizeof(ListNode));
ListNode* listB = (ListNode*)malloc(sizeof(ListNode));
append(listA, 2);
append(listA, 6);
append(listA, 9);
append(listA, 10);
printList(listA);
append(listB, 1);
append(listB, 5);
append(listB, 7);
append(listB, 8);
append(listB, 11);
printList(listB);
ListNode* result = mergeTwoLists(listA, listB);
printList(result);
}
main ํจ์์๋ ์์ ๊ฐ์ด ์ ๋ ฌ๋ ์ฐ๊ฒฐ ๋ฆฌ์คํธ 2๊ฐ๊ฐ ๋ฏธ๋ฆฌ ๋ง๋ค์ด์ ธ ์๋ค๊ณ ๊ฐ์ ํฉ๋๋ค. ์ฌ๋ฌ๋ถ์ด ์์ฑํ์ ํจ์ mergeTwoLists ํจ์, append ํจ์ ๊ทธ๋ฆฌ๊ณ printMergedLinkedList๋ฅผ ์์๋๋ก ํธ์ถํ๋ฉด ์ ๋ ฌ๋ ๊ฒฐ๊ณผ ์ถ๋ ฅ์ด ๋์ค๋๋ก ์์ฑํด ์ฃผ์ธ์.
A ๋ถ์์ B ๋ถ์์์ ๋ณด๋ด๋ ์ฐ๊ฒฐ๋ฆฌ์คํธ๋ ๋ชจ๋ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ๋์ด ์๋ ์ํ์ด๋ฉฐ, A ๋ถ์์์ ๋ณด๋ด์จ ๋ฆฌ์คํธ์ B ๋ถ์์์ ๋ณด๋ด์จ ๋ฆฌ์คํธ์ ๊ธธ์ด๋ ๋ค๋ฅผ ์ ์์ต๋๋ค.
์ ๋ ฅ๊ฐ: ์ ๋ ฌ๋ 2๊ฐ์ ์ฐ๊ฒฐ๋ฆฌ์คํธ(Main ํจ์์ ๋ฌธ์ ์ ๊ฐ์ด ์ ์ธ๋์ด ์๋ค๊ณ ๊ฐ์ )์ถ๋ ฅ๊ฐ: ์ ๋ ฌ๋ ๋ฆฌ์คํธ๊ฐ ์ถ๋ ฅ๋๊ฒ ํด์ฃผ์ธ์.
์์ ๋ฌธ์ ๋ผ๋ฉด, ๋ค์๊ณผ ๊ฐ์ด ์ถ๋ ฅ ๊ฐ์ด ๋์์ผ ํฉ๋๋ค.
2 6 9 10
1 5 7 8 11
1 2 5 6 7 8 9 10 11