참고
문제해설
NOTE
•
오름차순으로 정렬된 정수 배열 2개와, 각 배열의 개수를 나타내는 정수 2개가 주어진다.
•
감소하지 않는 순서로 정렬된 단일 배열로 nums1로 nums2를 병합한다.
•
0은 무시 해야 한다. ⇒ 크기를 초과하는 값은 0으로 표시되므로 병합할때 무시해야한다.
문제 로직고민
NOTE
•
기존 배열에 값을 옮겨야 한다
1.
기존에 존재하던 값들을 밀어내면서 병합해야하는가? ⇒ 별로 좋지않아 보임
2.
기존의 값들을 미리 다른 자료구조로 옮긴다음 병합해야하는가? ⇒ 이게 더 효율적인거 같다.
•
배열을 오름차순으로 병합한다.
◦
두 배열중 하나가 빌때까지 stack처럼 앞 idx부터 값을 병합하는 배열에 넣는다.
◦
단 넣는값은 두 배열중 작은값을 가지고 배열의 값을 넣는다.
◦
2개의 배열중 하나가 빈다면, 남은 배열의 모든값을 병합한다.
작성코드
NOTE
처음 제출한 코드
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
// 1. nums1의 배열을 다른 배열로 옮긴다 (단 0은 생략)
int[] nums3 = new int[m];
int num3_idx = 0;
for(int i : nums1){
if(i != 0 ) nums3[num3_idx++] = i;
if(num3_idx == m) break;
}
// 2. nums1에 nums2와 nums3의 값을 병합한다.
int num1_idx = 0;
int num2_idx = 0;
num3_idx = 0;
while(num3_idx != m && num2_idx != n){
int num3_value = nums3[num3_idx];
int num2_value = nums2[num2_idx];
if(num3_value >= num2_value) {
nums1[num1_idx] = num2_value;
num2_idx++;
}
else if(num3_value < num2_value) {
nums1[num1_idx] = num3_value;
num3_idx++;
}
num1_idx++;
}
// 3. 남은 배열값 모두 넣기
while(num3_idx != m){
nums1[num1_idx++] = nums3[num3_idx++];
}
while(num2_idx != n){
nums1[num1_idx++] = nums2[num2_idx++];
}
}
}
Java
복사
31/59 통과
•
제출하고나서 문제를 잘못이해했다는걸 깨달았다. 0을 모두 생략하는게 아니라, 개수를 초과하는 요소는 0으로 처리되니 무시하라는 의미였다.
•
위의 요소를 고려해서 다른 배열로 옮기는 코드를 수정했다.
통과코드
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
// 1. nums1의 배열을 다른 배열로 옮긴다 (단 0은 생략)
int[] nums3 = new int[m];
int num3_idx = 0;
for(int i : nums1){
if(num3_idx == m) break;
nums3[num3_idx++] = i;
}
// 2. nums1에 nums2와 nums3의 값을 병합한다.
int num1_idx = 0;
int num2_idx = 0;
num3_idx = 0;
while(num3_idx != m && num2_idx != n){
int num3_value = nums3[num3_idx];
int num2_value = nums2[num2_idx];
if(num3_value >= num2_value) {
nums1[num1_idx] = num2_value;
num2_idx++;
}
else if(num3_value < num2_value) {
nums1[num1_idx] = num3_value;
num3_idx++;
}
num1_idx++;
}
// 3. 남은 배열값 모두 넣기
while(num3_idx != m){
nums1[num1_idx++] = nums3[num3_idx++];
}
while(num2_idx != n){
nums1[num1_idx++] = nums2[num2_idx++];
}
}
}
Java
복사
•
위의 코드에서 0에 관련된것만 수정해서 바로 통과되었다.
•
사실 초반에 0이 모두 생략되어야 한다는 가정때문에 다른 자료구조로 옮기는 작업을 했는데, 지금 다시보니 필요없을거 같다.
정답코드
NOTE
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i =m-1;
int j = n-1;
int k = m+n-1;
while (i>=0 && j>=0) {
if (nums1[i]>nums2[j]) {
nums1[k--] = nums1[i--];
} else {
nums1[k--] = nums2[j--];
}
}
while (j>=0) {
nums1[k--] = nums2[j--];
}
}
}
Java
복사
메모리를 가장 적게 사용하는 코드
•
문제가 쉬운편이라 가장 최적의 풀이가 Memory로 3mb밖에 차이나지 않는다.
•
로직은 내가 진행한것과 반대로 큰값을 비교한거같은데 이게 더 효율적인거 같다.