티스토리 뷰
Question
두 개의 음이 아닌 integer type의 정수가 있는 linked list 가 주어질 때, 두 linked list의 합을 구하는 문제이다. linked list는 역순으로 저장되며, 답 또한 역순으로 출력해야 한다. 단, 주어진 list에서 0으로 시작하는 숫자는 없다고 가정한다. 즉, 숫자 003456과 같은 case는 없다.
제약사항
- 각 Linked List의 노드 개수는 [1,100] 이다.
- 각 노드의 값은 0 이상 9 이하이다.
- 숫자 0003456과 같이 0이 앞서는 list는 주어지지 않는다.
Solution
- 가능한 최선의 수행 시간(Best Conceivable Runtime(BCR))
두 리스트의 중 길이가 긴 리스트를 s라 할 때, 적어도 한 번은 모든 노드의 값을 확인해야 하기 때문에 시간 복잡도는 O(s)이다. - 고려사항
1. 두 리스트의 길이가 같지 않을 수 있다.
2. 두 리스트의 합은 두 리스트 중 긴 리스트보다 길어질 수 있다. - Solution 1 (Brute force)
어차피 두 수가 역순으로 주어지기 때문에 각 리스트의 처음부터 끝까지 탐색하며 더한 값을 새로운 노드의 값으로 하여 계속해서 추가해 나간다. 다만 더한 값이 10보다 carry가 발생하기 때문에 그 부분을 고려한다. 이런 식으로 해결 시 결국 시간 복잡도는 O(s)(s는 긴 리스트의 길이)로 BCR을 만족하기 때문에 시간 복잡도 측면에서 더 나은 알고리즘은 없다고 볼 수 있다.
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode();
ListNode* copy = dummy;
int carry = 0;
while (l1 || l2 || carry)
{
int l1_val = l1 ? l1->val : 0;
int l2_val = l2 ? l2->val : 0;
copy->next = new ListNode(((l1_val + l2_val + carry) % 10));
copy = copy->next;
if (l1) l1 = l1->next;
if (l2) l2 = l2->next;
carry = ((l1_val + l2_val + carry) >= 10) ? 1 : 0;
}
return dummy->next;
}
};
- Time complexity : O(s) // s는 두 리스트 중 긴 리스트의 길이
- Space Complexity : O(s+1) // 가능한 최대 리스트 길이 + carry 가 발생할 경우
문제 출처 : https://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
* 본 포스트 관련된 지적 및 조언은 모두 환영합니다.
'IT > Problem Solving' 카테고리의 다른 글
[C++] LeetCode : Longest Substring Without Repeating Characters (0) | 2022.07.06 |
---|---|
[C++] LeetCode : Sort Colors (0) | 2022.07.05 |
[C++] LeetCode : Letter Combinations of a Phone Number (0) | 2022.07.04 |
[C++] LeetCode : Binary Tree Inorder Traversal (0) | 2022.07.02 |
[C++] LeetCode : Group Anagrams (0) | 2022.06.30 |
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 트리
- PS
- 기술면접
- C++
- coding interview
- Medium
- 러스트
- 인터뷰
- 자료구조
- interview question
- LeetCode
- 알고리즘
- Interview
- Tree
- 러스트 배우기
- 솔직후기
- 내돈내산
- 속초 맛집
- 러스트 입문
- 맛집
- 러스트 기초
- Problem Solving
- 반드시 알아야 할 자료구조
- rust
- DP
- ProblemSolving
- 리트코드
- algorithm
- 코딩인터뷰
- 속초
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |
글 보관함