-
Leet code - 2. Add Two Number알고리즘/알고리즘 문제 복기 2021. 2. 8. 19:06
leetcode.com/problems/add-two-numbers/
Add Two Numbers - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
Answer1.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/class Solution {public:int carry = 0;ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* head = new ListNode();ListNode* temp = head;while(l1 != nullptr && l2 != nullptr) {int ret_value = l1->val + l2->val + carry;carry = 0;// 더한 값이 10을 넘을 경우 carry 처리if(ret_value / 10 > 0) {ret_value %= 10;carry += 1;// head에 아무것도 안들어있을 경우 처리if(head->next == nullptr) {head->next = new ListNode(ret_value);temp = head->next;}else {temp->next = new ListNode(ret_value);temp = temp->next;}}else {// head에 아무것도 안들어있을 경우 처리if(head -> next == nullptr) {head->next = new ListNode(ret_value);temp = head->next;}else {temp->next = new ListNode(ret_value);temp = temp->next;}}l1 = l1->next;l2 = l2->next;}// l1가 더 길 경우 l1만 처리while(l1 != nullptr) {int ret_value = l1->val + carry;temp->next = new ListNode(ret_value);carry = 0;if(ret_value / 10 > 0) {ret_value %= 10;carry += 1;// head에 아무것도 안들어있을 경우 처리if(head->next == nullptr) {head->next = new ListNode(ret_value);temp = head->next;}else {temp->next = new ListNode(ret_value);temp = temp->next;}}else {// head에 아무것도 안들어있을 경우 처리if(head -> next == nullptr) {head->next = new ListNode(ret_value);temp = head->next;}else {temp->next = new ListNode(ret_value);temp = temp->next;}}l1 = l1->next;}// l2가 더 길 경우 l2만 처리while(l2 != nullptr) {int ret_value = l2->val + carry;carry = 0;if(ret_value / 10 > 0) {ret_value %= 10;carry += 1;// head에 아무것도 안들어있을 경우 처리if(head->next == nullptr) {head->next = new ListNode(ret_value);temp = head->next;}else {temp->next = new ListNode(ret_value);temp = temp->next;}}else {// head에 아무것도 안들어있을 경우 처리if(head -> next == nullptr) {head->next = new ListNode(ret_value);temp = head->next;}else {temp->next = new ListNode(ret_value);temp = temp->next;}}l2 = l2->next;}if(carry > 0) {temp->next = new ListNode(carry);temp->next;}return head->next;}};cs 처음 풀어낸 코드. carry를 처리하는 부분과 head의 다음 부분이 비어 있을 때를 처리하는 부분이 불필요 했고
중복되는 코드도 많다.
Answer2.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081class Solution {public:int carry = 0;ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* head = new ListNode();ListNode* temp = head;while(l1 != nullptr && l2 != nullptr) {int ret_value = l1->val + l2->val + carry;carry = 0;// 더한 값이 10을 넘을 경우 carry 처리if(ret_value / 10 > 0) {ret_value %= 10;carry += 1;temp->next = new ListNode(ret_value);temp = temp->next;}else {temp->next = new ListNode(ret_value);temp = temp->next;}l1 = l1->next;l2 = l2->next;}// l1가 더 길 경우 l1만 처리while(l1 != nullptr) {int ret_value = l1->val + carry;temp->next = new ListNode(ret_value);carry = 0;if(ret_value / 10 > 0) {ret_value %= 10;carry += 1;temp->next = new ListNode(ret_value);temp = temp->next;}else {temp->next = new ListNode(ret_value);temp = temp->next;}l1 = l1->next;}// l2가 더 길 경우 l2만 처리while(l2 != nullptr) {int ret_value = l2->val + carry;carry = 0;if(ret_value / 10 > 0) {ret_value %= 10;carry += 1;temp->next = new ListNode(ret_value);temp = temp->next;}else {temp->next = new ListNode(ret_value);temp = temp->next;}l2 = l2->next;}if(carry > 0) {temp->next = new ListNode(carry);temp->next;}return head->next;}};cs 불필요한 부분을 덜어냈지만 여전히 코드가 너무 길어보였고 다른 사람이 한 해결책을 찾아보기로 했다.
Answer3.
1234567891011121314151617181920212223242526class Solution {public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {int sum = 0;ListNode* dummy = new ListNode(0), *cur = dummy;while(l1 || l2) {int val1 = l1 ? l1->val : 0;int val2 = l2 ? l2->val : 0;sum += val1 + val2;cur->next = new ListNode(sum % 10);sum /= 10;cur = cur->next;l1 = l1 ? l1->next : l1;l2 = l2 ? l2->next : l2;}if(sum)cur->next = new ListNode(sum);cur = dummy->next;delete dummy;return cur;}};cs 나는 l1과 l2가 Null인 것을 &&로 처리하여 해서 if문이 많이 필요했지만
이 사람은OR와 3항 연산자를 적극적으로 사용해서 세개를 한번에 처리 하는 식으로 진행했다.
'알고리즘 > 알고리즘 문제 복기' 카테고리의 다른 글
Leetcode - 17. Letter Combination of a Phone Number (0) 2021.02.13 Leetcode - 15. 3Sum (0) 2021.02.13 Leet code - 1. Two Sum (0) 2021.02.06 Leecode - 5. Logest Palindromic SubString (0) 2021.02.06 K번째 수 (0) 2021.02.03