LeetCode in C# 1. Two Sum

 

문제 요약

정수 숫자들이 담긴 배열과 목표 값이 주어졌을 때, 두 수를 더해서 목표 값이 되는 인덱스의 배열을 반환해라.

ex) [2, 7, 11, 15] , target = 9 라면, 2와 7을 더했을 때 9가 되므로 반환 값은 [0,1]

 

문제 핵심 (주관적인 생각)

모든 경우의 수를 다 더하는 것이 가장 쉬운 해결책이겠지만, 시간 복잡도를 더 줄일 수 있는 효율적인 탐색 알고리즘을 구현해야하는 것이 핵심이다.

 

풀이 방법 (1차)

뇌가 굳어서 방법이 떠오르지 않아, 그냥 모든 경우의 수를 전부 더해서 해결했다.

반복문을 통해, 두 수의 더한 값이 target이 될 때까지 앞에 자리 숫자부터 맨 뒤 숫자까지 반복적으로 더했다.

 

시간 복잡도 : O(n^2)

풀이 시간 : 19분 13초

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        
        //모든 경우의 수를 전부 계산해서 해결함.
        //최대값이 넘어가면 안되니까 -1
        for(int i = 0; i < nums.Length -1; i++)
        {
            for(int j = i + 1; j < nums.Length; j++)
            {
                int sum = nums[i] + nums[j]; 

                if(sum == target)
                {
                    return new int[2]{i, j};
                }
            }
        }

        return new int[0];
    }
}

 

풀이 방법 (2차)

해시 테이블 구조를 활용할 줄 아는것이 문제의 핵심이였다. 해시 테이블 자료형을 사용하면, 모든 요소를 순환하지 않아도 원하는 값에 접근할 수 있으므로 이 문제와 적합한 자료형이었던 것이다.

 

숫자를 key로 인덱스를 value로 1대1로 저장하여 문제를 해결하면 쉽고 효율적으로 문제 풀이가 가능하다.

ex) [2,7,11,15] 라면, Key : 2 이고 value : 0 으로 매칭을 시켜놓으면, 숫자값을 입력하면 인덱스를 반환하는 구조가 완성된다.

 

시간복잡도 : O(n)

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        //해시 테이블을 활용한 풀이
        Dictionary<int, int> map = new Dictionary<int, int>();

        for(int i = 0; i< nums.Length; i++)
        {
            int complement = target - nums[i]; //찾아야하는 값
            if(map.ContainsKey(complement)) //찾는 값이 존재하는지
            {
                return new int[] {map[complement], i};
            }
            map[nums[i]] = i;
        }
        
        return new int[]{};
    }
}

 

해시 테이블 자료형을 그동안 많이 사용해왔지만, 이 문제에 적용해볼 생각은 전혀하지 못했다.

특히 complement를 이끌어내는 공식인 target - nums[i]를 활용해볼 생각 또한 하지 못했다.

 

조금 더 넓은 시야를 가져야한다는 교훈을 얻게 해준 문제였다.