코딩테스트 #5

#5

정수 배열과 타겟 숫자가 주어지면, 합이 타겟값이 되는 두 원소의 인덱스를 찾으시오.

단, 시간복잡도 O(n) 여야 합니다.

예제)

Input: [2, 5, 6, 1, 10], 타겟 8

Output: [0, 2] // 배열[0] + 배열[2] = 8

for문을 두번 돌려서 간단하게 풀려 하였으나, 시간복잡도가 O(n)이다. 하긴 중첩 for문 처럼 쉬운 문제는 나오지 않겠지.... 어떻게 할까 고민하다가 Map을 사용하기로 하였다.

Map의 key에는 value(숫자) 값을 담고, value 에는 index 값을 담아서, value(숫자)에 해당하는 index를 추출하는 방식이다. Map(value, index)

for문을 돌면서 target 값에서 해당 value(숫자)를 뺀 후, 그 값이 Map에 존재하면 그 두 값의 인덱스를 리턴하고, 존재하지않으면 Map에 해당 (value(숫자), index)를 넣으면서 진행하는 방식이다.

 public int[] solution(int[] input, int target) {
        Map
 map = new HashMap();
        for(int i=0; i < input.length; i ++) {
            int subtraction = target - input[i];
            if(map.containsKey(subtraction)){
                return [map.get(subtraction), i];
            }
            map.put(input[i], i);
        }
        // 존재하지 않음 
        return null;
   }

글을 쓸때는 문제가 없는데 글을 올리면 코드 뒤에 </int,int> 태그 값이 붙네요.. 이유를 아시는분은 알려주시면 감사하겠습니다. (--)(__) 꾸벅