내가 작성한 코드 리뷰 - twoSum

🍊leetCode - twoSum

- Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

- You may assume that each input would have exactly one solution, and you may not use the same element twice.

- You can return the answer in any order.

twoSum문제유형은 많이 응용되고 있다.

이 문제를 푸는 방법은 Array + Map (고유키를 저장했다가 배열을 조건문을 돌려서 나오면 후려쳐서 값을 얻음) 이 대표적이다.

일단 아래의 방법은 이중for문을 돌린 것이다.
이렇게 구하면 사실 굉장히 쉽다. 직관적이고 알고리즘에 대해 그다지 지식이 많지 않는 초보가 처음에 쓰는 솔루션이다.
그러나 해당 방법은 O(n2)이 된다.

요소가 그다지 많지 않은 배열은 상관없겠지만 최악의 시나리오로 100만 ~ 1000만의 요소가 들어있다면 시스템에 무리가 갈 것이다.

그리하여 데이터 접근방식으로 Map을 이용해서 푸는 방법이 가장 효율적이라고 할 수 있겠다.

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

for문이 이중으로 돌아서 시간복잡도가 높다.

안에 if문 조건으로 " i !=j " 가 들어가지 않으면,

와 같은 오류가 난다.

즉 서로 다른 요소를 합한 것만 답으로 쳐주기 때문이다.

해당 솔루션은 99ms가 걸리며 더 시간을 줄이기 위해서 효율적인 코드를 짜는 것이 중요하다.

public static int[] twoSum(int[] nums, int target) {

		List<Integer> restOfTarget = new ArrayList<Integer>();

		int numSize = nums.length;

		for (int i = 0; i < numSize; i++) {

			int temp = target - nums[i];

			if (restOfTarget.contains(temp)) {

				return new int[] { restOfTarget.indexOf(temp), i };

			} else {
				restOfTarget.add(i, nums[i]);

			}
		}
		return new int[2];

이 솔루션은 맵과 비슷하게 ArrayList 즉 List를 이용해서 풀었다.

다음은 HashMap을 이용한 최종 솔루션.

public static int[] twoSumUsingHashMap(int[] nums, int target) {

		HashMap<Integer, Integer> restOfTarget = new HashMap<Integer, Integer>();

		for (int i = 0; i < nums.length; i++) {

			if (restOfTarget.containsKey(target - nums[i])) {

				return new int[] { restOfTarget.get(target - nums[i]), i };

			} else {
				restOfTarget.put(nums[i], i);
			}

		}

		return new int[2];

	}
	

hashMap을 이용한 것 뿐만아니라 직전 솔루션보다 훨씬 간결하게 작성했다.

또한 여기서 배열의 요소 값을 k로 인덱스를 v로 map에 저장했다.

여기서 필요한 건 해당 요소의 인덱스이기 때문이다.

• HashMap 특징 :
  키의 유무를 확인할 때 containskey()를 사용한다.
  요소를 넣을때 put(k.v)를 사용한다.
  값을 꺼낼때 get(k)를 사용한다.