leetcode 5. Input Array Is Sorted

허크·2023년 8월 27일

https://leetcode.com/problems/merge-sorted-array/?envType=study-plan-v2&envId=top-interview-150

167. Input Array Is Sorted

⭐ 문제

오름차순으로 정렬된 1-indexed 배열 numbers, 그리고 목표값 target이 주어졌을때 배열의 특정 두 값이 목표값이 되는 경우를 찾으세요. 단, 선택한 수는 같은 요소를 두번 사용해서는 안됩니다.

🤔 고려해야할 사항

'오름차순으로 정렬된' => 이미 크기순으로 정렬되어 있으므로 양 끝에서부터 계산해 나가는 것이 제일 효율적임
배열의 양끝에서부터 포인터 시작
두수의 합을 계산해서 포인터 이동
target 값과 동일하다면 값을 반환

✍️ 의사 코드

포인터 변수 초기화
포인터가 겹치는 순간까지 배열을 순회
포인터에 해당하는 두 값의 합계를 계산
2.1 합이 목표값보다 작으면 왼쪽포인터를 이동
2.2.합이 목표값보다 크다면 오른쪽포인터를 이동
그외의 경우는 같다는 소리 이므로 인덱스 값 반환

✅ 나의 풀이

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0; 
        int right = numbers.length - 1; 

        while (left < right) {
            int sum = numbers[left] + numbers[right]; 

            if (sum == target) {
                return new int[]{left + 1, right + 1};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }

        return new int[]{-1, -1};
    }
}

🖥️ 결과

Runtime 1ms

🤔 추가 질문

O(m + n)의 시간 복잡도를 가진 알고리즘으로 설계 할 수 있나요?

😰 나의 풀이 되돌아보기

1의 System.arraycopy(nums2, 0, nums1, m, n)의 시간 복잡도는 O(n)인데 2의 Arrays.sort(nums1)의 시간복잡도는 O(m * log m)의 복잡도를 가집니다. 즉 총합 시간 복잡도는 O(n + m * log m) 입니다.

🔥 개선을 위한 고민

문제를 차근차근 다시 읽어보았는데 nums1과 nums2가 이미 오름차순으로 정렬되어있다는 점이 눈에 띄었습니다. 이를 활용하여 시간복잡도 O(m * log m)의 Arrays.sort(nums1)를 사용하지 않고 해결한다면 더 빠르게 수행할 수 있을거 같습니다. 이를 위해서 1의 System.arraycopy가 아닌 전체적으로 새로운 풀이의 필요성이 느껴졌습니다.
1,2 2개의 과정으로 나누는 것이 아니라 하나의 동작으로 하려면 어떻게 해야하는지 고민해 보았습니다. 그 결과 정렬되어있는 두개의 정렬을 값을 비교하면서 알맞은 위치에 넣어준다는 하나의 동작으로 하면 어떨까라는 발상이 떠올랐습니다.
이를 위해선 이전에 부트캠프에서 사용하였던 두개의 배열을 동시에 다루는 투포인터 알고리즘이 적합한거 같았습니다.
투포인터 알고리즘으로 두 배열의 첫값부터 비교하면서 풀어볼려고 하니 생각되로 잘 되지 않았습니다. 그러던 중 고려해야할 사항에서 nums1의 배열 끝부분에는 nums2가 들어가기 위해 0의 값으로 입력되어 있다는 제약조건이 떠올랐습니다. 그렇다면 끝 값부터 정리해나가면 될거 같아서 이를 통해 새로운 풀이를 작성해 보았습니다.

✍️ 개선한 의사 코드

투포인터 알고리즘을 위한 두가지 포인터 pt1,pt2에 각 배열의 마지막 인덱스를 주입
pt2가 0이상인 경우 포인터가 지정한 인덱스 값을 계속하여 비교
2-1. 만약 pt1에 해당하는 값이 더 크거나 같다면 해당 값을 nums1의 마지막 값 즉 pt1 + pt2 + 1의 인덱스값에 넣기 그리고 pt1 감소
2-2. 그외의 경우 즉, pt2에 해당하는 값이 더 큰 경우에는 해당 값을 nums1의 마지막 값 즉 pt1 + pt2 + 1의 인덱스값에 넣기 그리고 pt2 감소

✅ 개선한 풀이

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        pt1 = m;
        pt2 = n;
		
        while (ptr1 >= 0 && ptr2 >= 0) {
            if (nums2[ptr2] > nums1[ptr1]) {
                nums1[ptr1 + ptr2 + 1] = nums2[ptr2];
                ptr2--;
            } else {
                nums1[ptr1 + ptr2 + 1] = nums1[ptr1];
                ptr1--;
            }
        }
        
        while (ptr2 >= 0) {
            nums1[ptr1 + ptr2 + 1] = nums2[ptr2];
            ptr2--;
        }
    }
}