All Articles

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

요즘 leetcode like top 100을 풀고 있는데 속도를 반드시 개선하고 싶은 문제를 발견했다.

21. Merge Two Sorted Lists

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

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 를 순회 하면서 값을 Listadd 하고
  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;
    }
}

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

이건 좀 자존심 상하는데.. 내가 하위 20%라니…

아 물론.. List 를 만들어서 value 를 저장하고 sorting 을 하고 이게 효율적인 알고리즘은 아닐 것이다. ㅠㅠ

분명히 누군가는 while 한번만 쓰고 끝냈을텐데

그래서 다음과 같은 기준을 정했다.

  1. while 은 딱 한번만 돌자
  2. sorting 은 내가 직접 한다.

두개를 비교해서 값을 할당하면 자연스럽게 sorting 이 되겠지?

while 을 딱 한번만 돌게 하려면 어떻게 해야할까?

l1, l2 가 둘 중 하나라도 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;
    }
}

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

아 코드가 너무 지저분한데… 똑같은 동작을 하는 코드를 if 문 안에서 or 로 묶는다면, 앞에 statement 늘 잘 돌고, 다음 값을 비교하는 condition 에서 NPE 가 발생한다.

[1,2,3]
[4,5,6]

이걸 더 줄여서 l1 을 result 에 넣었을 때, l2 값을 넣을까 했는데 그것도 말이 안된다. 위의 case 처럼 l1 이 먼저 모두 result 에 들어가고 l2 의 값들이 result 로 들어가는 케이스라면?

결국 이 방법이 가장 괜찮은것 같다