Grind75 - TwoSum

Grind 75를 통해서 처음으로 공부한 내용은 두개의 합을 구하는 배열의 문제였다. 

1. 문제

두 개의 합 문제

2. 나의 풀이

2.1 개념

2개의 합이 target과 같으려면 나는 모든 경우의 수를 더해보면 된다고 생각했다.

따라서 모든수의 합을 구하기위해 2중 반복문을 사용해서 배열의 요소를 접근하여 배열의 요소의 합이 target과 일치할경우 returnValue(결과값)에 넣고 break를 걸어서 끝내려 하였다.

2.2 코드

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int numLength = nums.length;
        int[] returnValue = new int[2];
        for(int i = 0; i < numLength; i++){
            for(int j =i+1; j<numLength; j++){
                if(nums[i] + nums[j] == target){
                    returnValue[0] = i;
                    returnValue[1] = j;
                    break;
                }
            }
        }
        return returnValue;
    }
}

 

3. 성능 평가

풀이시간 : 20분

성능 평가

 

4. 개선점

메모리의 경우 괜찮은 성능을 보였기때문에 크게 문제가 되지는 않는다고 생각했다 하지만 실행 시간의 경우는 개선이 어느정도 필요하다고 느껴진다. 따라서 다른 분들의 솔루션을 확인해서 개선된 방향을 확인하고자 한다.

 

5. 개선

개선을 위해 다른 분들의 풀이를 확인하였고, 2가지의 접근방법을 바탕으로 접근이 가능하다는 것을 확인하였다.

 

접근법

1. 무차별 대입방법(내가 사용한 방법)
- 무차별 대입 방법 중 하나는 모든 요소 쌍을 고려하고, 그 합이 목표와 같은지 확인하는 것이다. 이는 중첩 루프를 사용하여 수행할 수 있으며, 여기서 외부 루프는 첫 번째 요소에서 . 두번째로 마지막 요소까지 반복하고 내부 루프는 다음 요소에서 마지막 요소까지 반복한다. 그러나 이 방법은 반복문이 2개로 시간 복잡도가 O(n^2)이다.

 

2. 해시테이블

- 더 효과적인 접근 방식은 해시테이블을 이용하는 것이다. 배열을 한번 반복하고 각 요소에 대한 대상에서 현재 요소를 뺀값이 해시 테이블에 있는지 확인할 수 있다. 존재한다면 유효한 숫자 쌍을 찾은것이고, 존재하지 않으면 현재 요소를 해시테이블에 추가한다.

 

해시테이블을 사용한 접근 방식

1. 요소와 해당 인덱스를 저장하기 위해 빈 해시 테이블을 만든다.

2. 배열을 왼쪽에서 오른쪽으로 반복한다.

3. 각 요소 nums[i]에 대해 대상에서 빼서 보수를 계산한다.(보수 = target - nums[i])

4. 해시테이블에 값이 존재하는지 확인한다.

5. 해시테이블에 보수가 없으면 현재요소 nums[i]를 해당 인덱스 값으로 하여 해시 테이블에 추가한다.

6. 해결법을 찾거나 배열의 끝에 도달할 때까지 3~5를 반복한다.

7. 해결법이 발견되지 않는다면 빈배열을 반환한다.

 

해시 테이블의 접근방식은 해시 테이블 조회가 평균적으로 일정한 시간이 걸리기 때문에 O(n)의 시간 복잡도를 갖는다. 이를 통해 배열을 한번만 통과해서 문제를 해결할 수 있다.

개선 코드

class Solution {
    public int[] twoSum(int[] nums, int target) {
        //해시 맵을 만든다.
        //해시맵의 key : 각 nums[i]의 값을 저장 value : 각 nums[i]의 인덱스 즉 i를 저장
        Map<Integer, Integer> numMap = new HashMap<>();
        int n = nums.length;

        //배열을 순회하면서 목표값에서 현재 지금 조회한 nums[i]의 값을 뺐을때 그 값이 해시맵에 존재하는지 확인한다.
        for (int i = 0; i < n; i++) {
            int complement = target - nums[i];
            if (numMap.containsKey(complement)) {       // target에서 현재값을 뺀값이 현재 HashMap에 있는지 확인한다.
                return new int[]{numMap.get(complement), i};    //있다면 배열을 반환하는데{보수값의 인덱스,현재 인덱스}의 형태로 반환한다.
            }
            numMap.put(nums[i], i); // target에서 현재값을 뺀값이 현재 HashMap에 없다면 현재의 값과 인덱스를 HashMap에 추가한다.
        }
        return new int[]{}; //아무것도 찾지 못했다면 빈 배열을 반환한다.
    }
}

 

위와같은 코드로 개선을 하였고 실행속도가 상위권에 위치되는것을 확인했다.

해당 내용을 반복 숙달 할 수 있도록 2주뒤에 다시 풀어보면 좋을것 같다.