리트코드 - 167. Two Sum II - Input Array Is Sorted

리트코드 - 167. Two Sum II - Input Array Is Sorted

출처 - https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

주어진 1부터 시작하는 정수 배열 numbers는 이미 비내림차순으로 정렬되어 있습니다. 이 배열에서 두 숫자를 찾아야 하는데, 이 두 숫자의 합이 특정한 목표 숫자(target)가 되어야 합니다. 이 두 숫자를 numbers[index1]과 numbers[index2]라고 하며, 여기서 1 <= index1 < index2 < numbers.length 조건을 만족해야 합니다.

두 숫자의 인덱스인 index1과 index2를 찾아서, 1을 더한 [index1, index2]라는 정수 배열로 반환해야 합니다. 이때, 테스트는 정확히 하나의 해결책이 있다는 전제하에 생성되었습니다. 같은 요소를 두 번 사용할 수 없습니다.

해결책은 오직 상수 크기의 추가 공간만 사용해야 합니다.

 

의사코드

크기 2짜리 배열 생성 왼쪽 포인터  = 0 오른쪽 포인터  = 배열 길이 - 1 반복문 시작 [왼쪽이 오른쪽보다 커지면 종료]     if 배열 왼쪽 + 오른쪽 = target         왼쪽 + 1         오른쪽 + 1           else if 배열 왼쪽 + 오른쪽 > target         오른쪽 - 1     else          왼쪽 + 1  반복문 종료

풀이코드

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

        while (left < right) {
            if (numbers[left] + numbers[right] == target) {
                answer[0] = ++left;
                answer[1] = ++right;
                break;
            } else if (numbers[left] + numbers[right] > target) {
                right--;
            } else {
                left++;
            }
        }
        return answer;
    }
}

코드설명

문제를 요약하면, 배열 내에서 두 수의 합이 특정 값이 되는지를 묻는 문제이다.

투포인터를 사용해서 문제를 해결한다.

 

왼쪽과 오른쪽 인덱스를 생성하여 두 인덱스에 있는 배열의 값을 더한다.

만약 target값과 같으면 각각의 인덱스에 1을 더하고 반복문을 종료한다.

 

오름차순으로 정렬되어 있는 배열이기 때문에(정확히는 중복값이 있는 오름차순) 더한 값이 target값보다 크면,

큰 값을 줄이기 위해 right를 하나 -1 해준다.

반대로, target값보다 작은 경우 left를 +1 해준다.

 

이렇게 반복하다보면 target 값을 만나고 종료되게 된다.

 

시간복잡도 - O(log n)

공간복잡도 - O(1)

문제를 풀며 생각한 흐름과 배운 점

수업에서 투포인터 개념을 배울 때 사용했던 예제와 같아서 아이디어 자체를 떠올리는 데는 쉬웠다.

시간복잡도도 괜찮은 편이고 공간복잡도도 나쁘지 않은 것 같다.

 

조금 더 간결하게 작성할 수도 있기는 하다.

리팩토링

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

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

코드의 길이가 줄었을 뿐 큰 차이는 없다.

 

다른코드

class Solution {
    public int[] twoSum(int[] numbers, int target) {
       int first= 0;
       int last = numbers.length-1;
       
       while(first<=last)
       {
        
           if(numbers[first]+numbers[last]<target)
           {
               first++;
           }
           else if(numbers[first]+numbers[last]>target)
           {
               last--;
           }
           else
           {
               System.gc();
               return new int[] {first+1, last+1};
               
           }
       } 
       return new int[] {};
		}
}

c언어에서 저렇게 중괄호를 줄 바꾸고 쓰던데 c언어를 자주 쓰는 사람의 코드인가보다.

투포인터를 똑같이 쓰고 있지만 특이한 부분이 System.gc()인데 이게 무슨 메소드인가 해서 봤더니 가비지 컬렉터 호출 메소드다.

 

위 코드는 메모리가 3mb 정도 적게 들길래 내 코드에 이 메소드만 추가해봤더니 내 것도 3mb가 줄었다.

 

자바에서는 가비지 컬렉터가 자동으로 사용하지 않는 리소스를 없애준다고 알고 있었는데 직접 호출하는 것과 무슨 차이가 있을까?

이와 관련해서는 아래 블로그에 잘 정리되어있다.

 

가비지 컬렉션 동작 원리 & GC 종류 💯 총정리

 

상당히 많은 내용이 적혀있는데 핵심적인 부분은 이것이다.

 

1. JVM의 가비지 컬렉터는 heap영역을 돌아보며 unreachable한 객체를 지운다.

2. 하지만 가비지 컬렉터의 호출 시점은 정확하게 알기 어렵다.

 

즉, 위 코드는 가비지 컬렉터를 임의로 불러온 것인데 자바에서는 JVM에 메모리 관리를 위임하고 코드에 집중하고자 하는 언어이기 때문에 필요한 경우가 아니라면 gc를 호출하지 않는 것이 맞는 것 같다.

 

억지로 메모리를 줄일려고 만든 코드가 아닐까.

 

정리

투포인터에 대한 익숙한 사용이었다.