[LeetCode] 23번 문제를 풀어보았다. (ft. java)

2022년 2월 05일 토요일 - 히히 쉬는 날이 젤 조아

오늘 올려볼 문제는 23번 Merge k Sorted Lists 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

Hard라는 글자를 보자마자 오늘은 블로그에 글 못올리나 했다..

입력

사진에서도 볼 수 있듯이 정렬된 링크드 리스트 배열이 주어진다.

---

풀이 및 코드

정렬된 링크드 리스트 들을 하나로 merge 하는 문제이다.

오늘은 처음부터 정답을 생각해냈다.

링크드 리스트에 들어있는 값의 범위가 -10,000 부터 10,000까지라서 크기가 20,005 int 배열을 하나 만들었다.

각 인덱스에 해당하는 숫자의 개수를 저장하는 배열로 사용한다.

모든 링크드 리스트에 들어있는 숫자를 인덱스로 사용하여 배열에 개수를 저장한다.

마지막으로 배열을 순회하면서 개수만큰 해당 인덱스를 링크드 리스트에 넣는 방법으로 구현했다.

이런식으로 시간복잡도 O(N)에 풀 수 있는 방법을 생각해냈다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // 결과 저장할 ListNode
        ListNode head = new ListNode();
        ListNode node = head;

        // 숫자 개수를 저장할 배열
        int[] result = new int[20005];

        for(int i = 0; i < lists.length; i++)
        {
            while(lists[i] != null)
            {
                // 10000을 더하는 이유는 -10000까지 값이 있기 때문
                result[10000 + lists[i].val]++;

                lists[i] = lists[i].next;
            }
        }

        // 인덱스에 해당하는 숫자의 개수만큼 링크드 리스트에 넣어준다.
        for(int i = 0; i < result.length; i++)
        {
            while(result[i] > 0)
            {
                node.next = new ListNode();

                node = node.next;

                node.val = i - 10000;

                result[i]--;
            }
        }

        // 처음 노드에는 아무 값도 안넣는 식으로 구현했기 때문에 next를 리턴한다.
        return head.next;
    }
}

---

제출 화면

오늘은 hard 문제라서 순간 겁을 먹었던 문제였다.

다행히 제약조건이 깐깐한 편이 아니라서 그나마 쉽게 풀 수 있었던 것 같다.

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.