Leetcode 21.Merge Two Sorted Lists 풀이 속도를 개선해보자

태그
Leetcode
ListNode
Algorithm
Easy
공개여부
작성일자
2020/06/29
요즘 leetcode like top 100을 풀고 있는데 속도를 반드시 개선하고 싶은 문제를 발견했다.
leetcode-21.merge-two-sorted-lists-%E1%84%91%E1%85%AE%E1%86%AF%E1%84%8B%E1%85%B5-%E1%84%89%E1%85%A9%E1%86%A8%E1%84%83%E1%85%A9%E1%84%85%E1%85%B3%E1%86%AF-%E1%84%80%E1%85%A2%E1%84%89%E1%85%A5%E1%86%AB%E1%84%92%E1%85%A2%E1%84%87%E1%85%A9%E1%84%8C%E1%85%A1.png
Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.
Example:
Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4
맨 처음 생각한 풀이는
1.
ListNode 를 순회 하면서 값을 List 에 add 하고
2.
sorting 을 실행 한 뒤에
3.
그 값을을 다시 순회하면서 ListNode 를 만들어 반환하면 되겠다
라고 생각했다.
class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null && l2 == null) return null; List<Integer> nums = new ArrayList<>(); while (Objects.nonNull(l1)) { nums.add(l1.val); l1 = l1.next; } while (Objects.nonNull(l2)) { nums.add(l2.val); l2 = l2.next; } Collections.sort(nums); ListNode result = new ListNode(nums.get(0)); ListNode node = result; for (int i = 1; i < nums.size(); i++) { node.next = new ListNode(nums.get(i)); node = node.next; } return result; } }
Java
leetcode-21.merge-two-sorted-lists-%E1%84%91%E1%85%AE%E1%86%AF%E1%84%8B%E1%85%B5-%E1%84%89%E1%85%A9%E1%86%A8%E1%84%83%E1%85%A9%E1%84%85%E1%85%B3%E1%86%AF-%E1%84%80%E1%85%A2%E1%84%89%E1%85%A5%E1%86%AB%E1%84%92%E1%85%A2%E1%84%87%E1%85%A9%E1%84%8C%E1%85%A1-2.png
이건 좀 자존심 상하는데.. 내가 하위 20%라니…
아 물론.. List 를 만들어서 value 를 저장하고 sorting 을 하고 이게 효율적인 알고리즘은 아닐 것이다. ㅠㅠ
분명히 누군가는 while 한번만 쓰고 끝냈을텐데
그래서 다음과 같은 기준을 정했다.
1.
while 은 딱 한번만 돌자
2.
sorting 은 내가 직접 한다.
두개를 비교해서 값을 할당하면 자연스럽게 sorting 이 되겠지?
while 을 딱 한번만 돌게 하려면 어떻게 해야할까?
l1l2 가 둘 중 하나라도 null 상태가 아니라면, 계속 while 이 돌도록 해야겠다. (아 그럼 2n2n 이 되는건가..?) 나중에 생각해야지
class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null && l2 == null) return null; ListNode result = new ListNode(-100); ListNode node = result; while (l1 != null || l2 != null) { if ( l1 == null ) { node.next = new ListNode(l2.val); l2 = l2.next; } else if (l2 == null){ node.next = new ListNode(l1.val); l1 = l1.next; } else if (l1.val >= l2.val) { node.next = new ListNode(l2.val); l2 = l2.next; } else if (l1.val < l2.val) { node.next = new ListNode(l1.val); l1 = l1.next; } node = node.next; } return result.next; } }
Java
leetcode-21.merge-two-sorted-lists-%E1%84%91%E1%85%AE%E1%86%AF%E1%84%8B%E1%85%B5-%E1%84%89%E1%85%A9%E1%86%A8%E1%84%83%E1%85%A9%E1%84%85%E1%85%B3%E1%86%AF-%E1%84%80%E1%85%A2%E1%84%89%E1%85%A5%E1%86%AB%E1%84%92%E1%85%A2%E1%84%87%E1%85%A9%E1%84%8C%E1%85%A1-3.png
아 코드가 너무 지저분한데… 똑같은 동작을 하는 코드를 if 문 안에서 or 로 묶는다면, 앞에 statement 늘 잘 돌고, 다음 값을 비교하는 condition 에서 NPE 가 발생한다.
[1,2,3] [4,5,6]
Java
이걸 더 줄여서 l1 을 result 에 넣었을 때, l2 값을 넣을까 했는데 그것도 말이 안된다. 위의 case 처럼 l1 이 먼저 모두 result 에 들어가고 l2 의 값들이 result 로 들어가는 케이스라면?
결국 이 방법이 가장 괜찮은것 같다
Made with 💕 and Oopy