반응형
안녕하세요. Ruk 입니다. Median of Two Sorted Arrays 문제에 대하여 풀이를 한번 써보려고 해요.
이번 문제는 난이도가 Hard이지만 easy처럼 느껴지는 이상한 문제였내요.
문제의 조건은 조건은 입력받은 두 배열을 머지하여 중앙값의 평균을 구하는 문제였습니다.
- nums1.length == m
- nums2.length == n
- 0 <= m <= 1000
- 0 <= n <= 1000
- 1 <= m + n <= 2000
- -106 <= nums1[i], nums2[i] <= 106
문제에서 주어진 조건인데, 두 배열의 길이합은 최소 1이고
배열안의 값고 106이니 int형 범위안에서 해결이 가능합니다.
소수점만 고려하면 되겠군요.
생각보다 풀이는 간단합니다.
1. 두 배열값을 비교하며 순차적으로 머지 시킵니다.
2. 머지된 리스트 길이가 짝수, 홀수에 따라 중앙값을 구해서 반환합니다.
위 조건을 고려해 코드로 짜보면
i, j 값을 0부터 시작하여 nums1과 nums2값을 비교해서 작은값을 넣어줌니다.
이때 b(n)만큼의 시간복잡도가 걸리겠군요.
nums1 or nums2중 아직 값이 남은 배열이 있다면 추가 while문을 돌립니다.
이렇게 정렬된 배열 nums3를 가지고 결과를 반환합니다.
짝수라면 중앙값 2개를 합쳐서 /2 처리를 합니다. 이때 소수점이 생길 수 있겠죠? double형 변환은 필수입니다.
홀수라면 중앙값 1개만 반환하면 되니 간편하네요.
코드를 다 짜고 놓치는 예외케이스가 있나 걱정했지만 테스트 결과 속도, 메모리, 케이스 까지 무난하게 통과되었내요.
반응형
'알고리즘 > LeetCode' 카테고리의 다른 글
| LeetCode[Java] - Next Permutation 풀이 (0) | 2021.04.06 |
|---|---|
| LeetCode[Java] - Integer to Roman 풀이 (0) | 2021.04.03 |
| LeetCode[Java] - Longest Palindromic Substring 풀이 (0) | 2021.04.01 |
| LeetCode[Java] - Longest Substring Without Repeating Characters 풀이 (0) | 2021.04.01 |
| LeetCode[Java] - Add Two Numbers 풀이 (0) | 2021.04.01 |