릿코드(LeetCode) int 배열 코딩테스트(two sum) 문제 및 풀이

개발자로 취업을 하기 위해서는 코딩 테스트 준비를 하는 것이 좋습니다. 특히나 국내 및 해외의 대기업을 노리신다면 코딩 테스트는 거의 필수인데요. 코딩 테스트로 유명한 LeetCode 사이트의 초급 문제 및 정답을 간단히 풀이하도록 하겠습니다. 코딩 실력을 올리는 것에는 여러 가지 방법이 있지만, 좋은 코드를 보는 것만으로도 실력이 올라갈 수 있습니다. 그럼 바로 문제를 보도록 하겠습니다.

 

목차

코딩 테스트 문제

LeetCode 문제

릿코드(LeetCode)가 코딩 테스트 사이트로 아주 유명하지만, 해외 사이트인 만큼 모든 문제들은 영어로 되어 있습니다. 그래도 크게 걱정하지 않으셔도 됩니다. 번역기를 써서 간단히 번역하여 문제를 풀면 됩니다. 번역한 문제는 아래와 같습니다.

 

문제

정수 및 정수 대상의 배열이 주어지면 두 숫자의 인덱스를 대상에 반환합니다.
각 입력에는 정확히 하나의 솔루션이 있으며 동일한 요소를 두 번 사용하지 않을 수 있다고 가정할 수 있습니다.
어떤 순서로든 답변을 반환할 수 있습니다.

 

예시 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

 

예시 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:

 

예시 3:
Input: nums = [3,3], target = 6
Output: [0,1]

 

문제와 출력 값 예시를 통해서 간단히 문제를 파악할 수 있습니다.

각 배열에 들어가 있는 값의 합이 target(목표값)과 일치할 때 그 각각의 배열 위치 정보를 반환해라는 것입니다.

 

 

코딩 테스트 정답 코드 1

정답입력란

기본적으로 나와있는 코드는 위 사진과 같습니다.

언어는 직접 선택이 가능한데요. 많은 사람들이 사용하고 있는 Java로 문제를 풀어보도록 하겠습니다.

우선 가장 단순하게 생각하면 모든 배열의 값을 각각 더해서, 목표값과 일치하면 각각의 배열 위치를 반환하면 됩니다.

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

위 코드로 결과값을 돌려보면 아래와 같이 됩니다.

제출 결과(파파고 번역분)

 

위와 같은 코드가 되지만, 이중 포문을 쓰고 처음부터 끝까지 배열 안의 모든 값들을 일일이 대조한다는 것이 아무래도 효율성 측면에서 좋지 않습니다. 결과값을 보아도 런타임 시간이 47ms이 걸린 것을 볼 수 있습니다. 조금 더 나은 코드를 생각해 보면 아래와 같습니다.

코딩 테스트 정답 코드 2

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

이번에는 해쉬 맵을 사용하여 맵의 키값을 확인하는 방식을 사용하였습니다.

For문을 한 번만 사용하여 속도를 높였습니다.

맵의 키값에 Int배열의 값을 입력하고, value값에 Int배열의 자리수를 입력합니다.

map.containsKey()기능을 사용하여 목표값 (target)에서 number Int배열의 값을 뺀 수를 가지고 있는 key값이 맵 안에 있는지 확인합니다.

key값이 있으면 그 key값의 int number 배열의 자리수, 즉 map의 value 값을 return값의 첫배열(0)으로 입력하고 이후 나머지 배열의 자리수를 나타내는 i를 2번째 배열에 입력하여 반환하게 되는 기능입니다. 

해쉬 맵의 입력기능도 동시에 같은 반복문안에서 처리 하고 있습니다.

2번째 코드의 제출결과

이번에는 보는 것과 같이 제출한 코드의 런타임 시간이 1ms로 이전에 제출한 코드의 47ms 보다 엄청나게 시간이 줄어든 것을 확인할 수 있습니다. 그럼 여러분의 코딩이 더욱 즐거워지기를 기원하면서 마치겠습니다.