리트코드 21. Merge Two Sorted Lists JAVA

문제

문제 해석

이번에는 재귀를 이용해서 문제를 풀려고한다.
초기 수도 코드 -> 변경 수도코드 -> 코드 이런식으로 문제를 해석해보려고한다.

수도코드 변천사

초기 수도 코드

    수도 코드
        private ListNode getSortedNode(ListNode list1, ListNode list2)
            재귀 탈출 조건
            if(list1 == null && list2 == null)
                return null;
            list1 list 둘 다 null이 아닐 때
                if list2이 더 클 때
                return new ListNode(list1.val, getSortedNode(list1.next,list2))
                if list1이 더 클 때
                return new ListNode(list2.val, getSortedNode(list1,list2.next))
            list1만 null일 때
                return new ListNode(list1.val, getSortedNode(list1.next,list2))
            list2만 null일 때
                return new ListNode(list2.val, getSortedNode(list1,list2.next))

이 수도 코드의 문제나나 너무 많은 return을 가지고 있다.
간단하게 간소화 하기 위해서 변수를 추가

변수 사용해 간소화 한 수도 코드

    수도 코드
        private ListNode getSortedNode(ListNode list1, ListNode list2,int num)
            재귀 탈출 조건
            if(list1 == null && list2 == null)
                return null;
            list1 list 둘 다 null이 아닐 때
                if list2이 더 클 때
                    num = list1.val;
                    list1 = list1.next;
                if list1이 더 클 때
                    num = list2.val;
                    list2 = list2.next;

            list1만 null일 때
                num = list2.val
                list2 = list2.next;
            list2만 null일 때
                num = list2.val;
                list2 = list2.next;

            return new ListNode(num, getSortedNode(list1,list2,num));

변수를 사용해서 데이터를 넣어주고 마지막에 한번 리턴을 호출해준다.
위의 코드에서 더욱 간소화 할 수 있는 조건이 있는지 확인해본다.

둘 다 빈 값일 경우 가장 첫 조건문에서 탈출이 된다.
그렇기 때문에 우리가 체크할 가지수는 3가지다.

1. 오직 list1 == null
2. 오직 list2 == null
3. list1 != null list2 != null

이렇게 만들어 두면 코드를 더 간소화 할 수 있다.

if 조건문 재정렬

       private ListNode getSortedNode(ListNode list1, ListNode list2,int num)
            재귀 탈출 조건
            if(list1 == null && list2 == null)
                return null;

           list1만 null일 때
                num = list2.val
                list2 = list2.next;

            list2만 null일 때
                num = list2.val;
                list2 = list2.next;

            if list2이 더 클 때
                num = list1.val;
                list1 = list1.next;

            if list1이 더 클 때
                num = list2.val;
                list2 = list2.next;

            return new ListNode(num, getSortedNode(list1,list2,num));

위의 코드를 보면 list1, list2가 모두 존재하는지 검증하는 if문이 빠져있다.
어차피 위의 3개의 조건을 만족시키면서 내려오면 무조건 list1, list2는 존재하기 때문이다.
이 수도 코드를 가지고 코드를 구현해보자

코드

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        return getSortedNode(list1,list2);
    }
    private ListNode getSortedNode(ListNode list1, ListNode list2){
        int num  = Integer.MAX_VALUE;
        //재귀 탈출 조건
        if(list1 == null && list2 == null)
            return null;

        if(list1 == null){
           num = list2.val;
            list2 = list2.next;
        }  
        else if(list2 == null){
            num = list1.val;
            list1 = list1.next;
        }
        else if (list1.val <= list2.val){
            num = list1.val;
            list1 = list1.next;
        }    
        else if (list1.val > list2.val){
            num = list2.val;
            list2 = list2.next;
        }
        return new ListNode(num, getSortedNode(list1,list2));
    }

위의 코드를 보면 간소화를 했다.
수도코드에서 변경사항은 파라미터로 들어가는 num을 변수로 빼냈다.

실행 속도는 다음과 같다.

회고

수도 코드를 일단 적고 점차 간소화 하는 과정으로 포스팅을 해봤다.
엣날 풀었던 방식처럼 수도코드를 계속 만들면서 수정하고 수정하다 보면 내가 뭘 수정했는지 까먹기도 했는데 이렇게 내가 어떤 생각을 가졌는지 다시 한번 확인해보는 과정이 문제 풀이에 도움이 더 되는 것 같다.

그리고 코드를 다 완성 시키고 변경하는 것도 도움이 되지만 내가 정확하게 어떤 코드를 짜야하는지 아는 경우에는 수도 코드로 변경을 하는것이 시간 단축에도 도움이 되는 것 같다.