[문제 출처]
LeetCode - Merge Sorted Array
문제 이해
m과 n은 두 배열이 합쳐질 때 어떤 영향을 미치는지에 대한 이해가 어려웠습니다.
주어진 조건인 nums1.length == m + n을 고려하는 것이 중요합니다.
이 문제에서 nums1 배열이 주된 배열이며, 배열 nums1의 앞부분 m개는 그대로 유지하되, 나머지 공간은 nums2 배열의 요소로 대체해야 합니다.
m은 첫 번째 배열 nums1의 앞부분 m개를 의미하며, 이 부분은 변경되지 않아야 합니다. 그러나, m 이후의 인덱스부터는 nums2 배열의 요소로 대체되어야 합니다.
접근방식 및 풀이방법
STL 사용
1. 기준이 되는 nums1 배열의 원소 m개 까지는 무조건 고정
2. m번째 인덱스부터 nums2 배열의 값을 담아주기 (n개)
3. for문이 끝나서 배치가 완료되면 Arrays.sort() 이용하여 정렬
내가 작성한 코드
복잡도
Time Complexity(시간 복잡도):
- O((m+n)log(m+n)): sort() 함수 사용으로 인한 시간 소요
- 정렬 알고리즘의 특성에 따라 배열의 크기에 비례하는 시간이 소요됨
Space Complexity(공간복잡도):
- O(1): 추가 공간을 사용하지 않음
참고 자료
"비내림차순과 오름차순은 같은 의미일까? 에 대한 토론"
https://www.acmicpc.net/board/view/109450
- non-decreasing order (비내림차순)
-> 점점 증가하는 수열
-> 인접한 두 수가 같을 수 있는지의 여부를 알려주고 있지 않을 때 - decreasing order (내림차순)
- increasing order (오름차순)
- strictly increasing (엄격히 증가하는)
-> 두 수가 같으면 안되는 항상 증가하는 수열
"비내림차순(non-decreasing order)"과 "오름차순(increasing order)"은 수열의 특성을 나타내는 용어입니다.
비내림차순은 점점 증가하는 수열을 의미하지만, 중복된 값이 있을 수도 있습니다. 반면에 오름차순은 중복된 값이 없으며 항상 증가하는 수열을 의미합니다.
문제에서 요구하는 비내림차순의 개념은 중복된 값이 있을 수 있으나 일반적인 오름차순 순서와 같습니다. 따라서 중복된 값이 있을 때도 정상적으로 처리될 수 있습니다.
그래서 해당 문제에서는 비내림차순(non-decreasing order) 용어를 선택했으며, 이는 주어진 조건을 더 명확하게 설명할 수 있도록 도와준 것 같으면서도 헷갈리게 한 것 같기도 합니다.
