.leetcode(167. Two Sum II - Input Array Is Sorted)

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

 

1. 2022.01.05 시도

소요시간: 9분(map), 9분(array)

# map
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        Map<Integer, Integer> temp = new HashMap<>();
        for(int x=0; x<numbers.length; x++) {
            if (temp.containsKey(numbers[x])) {
                return new int[]{temp.get(numbers[x])+1, x+1};
            }
            
            int diff = target - numbers[x];
            temp.put(diff, x);
        }
        
        return new int[2];
    }
}

# array
class Solution {
    private static int DUMMY = 2000;

    public int[] twoSum(int[] numbers, int target) {
        int[] temp = new int[4001];
        
        // counting
        for (int x=0; x<numbers.length; x++) {
            temp[DUMMY+numbers[x]]++;
        }
        
        int[] ret = new int[2];
        for(int x=0; x<numbers.length; x++) {
            int diff = target - numbers[x];
            if ((diff * 2 == target && temp[DUMMY+numbers[x]] == 2)
                || (temp[DUMMY+diff] == 1)) {
                ret[0] = x+1;
                target = diff;
                break;
            }
        }
        
        for(int x=ret[0]; x<numbers.length; x++) {
            if (target == numbers[x]) {
                ret[1] = x+1;
                break;
            }
        }
        
        return ret;
    }
}

풀이 접근 과정

Two sum 문제랑 다른건 정렬 밖에 없다고 생각했다. 그래서 이전 정렬안된 방식도 충분히 빠른 O(n)방식이라고 생각되었고 n개를 읽어야지만 풀 수 있는 것이라 판단되어 map을 이용한 시간복잡도 O(n)의 풀이를 안할 이유가 없어서 바로 코딩하였다.

map용 풀이를 진행하면서 지난 array로 풀다가 OOM이 나왔던 생각이 나서 제한조건을 살펴보니 이번에는 굉장히 작았다. target과 numbers[i가 -1000이상 1000이하 였기에 충분히 array에 담을 수 있겠구나 싶었다. array를 이용하면 코드는 복잡해지만 시간복잡도는 O(n)으로 동일하면서도 4001개의 array만 사용하므로 상수로 취급되어 공간복잡도는 O(1)로 만들 수 있겠다 싶었다.

 

느낀점

• 두  해법모두 정렬이라는 장점을 이용하는 해법은 아니라는 판단이 들어서 조금 찜찜했다. 솔루션을 보면서 생각해보니 정렬되었으면 포인터만으로도 풀이법을 생각해볼 수 있구나라는 생각을 했다. 배열로 풀었을 때 따로 선언하지 않고도 풀 수가 있다.

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int x=0;
        int y=numbers.length-1;
        while(true) {
            int sum = numbers[x] + numbers[y];
            if (sum > target) {
                y--;
            } else if (sum < target) {
                x++;
            } else {
                break;
            }
        }
    
        return new int[]{x+1, y+1};
    }
}

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형