[코딩테스트] LeetCode - Two Sum (성공)

 

Two Sum - LeetCode

 

 

풀이

배열 nums에서 nums[i] + nums[j] == target을 만족하는 (i, j)를 찾아 반환하는 문제다. 

nums 배열의 길이는 최대 10^4 = 10,000이다. 

O(N^2) 풀이는 10,000 * 10,000 = 100,000,000 = 1억번의 연산이 일어난다. 

컴퓨터는 1억번 연산을 1초에 한다. 따라서 O(N^2) 풀이로 풀어도 괜찮겠다. 

O(N^2) 풀이를 생각해보자. 

 

그냥 간단하다. 

nums[i]와 nums[i+1], nums[i+2], ... 와 비교해서 두 수의 합이 target인 i와 j를 구하면 된다. 없으면 

nums[i+1]와 nums[i+2], nums[i+3], ... 와 비교해서 두 수의 합이 target인 i와 j를 구하면 된다.

이런식으로 진행하면 되고 이게 O(N^2) 풀이가 되겠다. 

 

 

코드1 - 정답 

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        // O(N^2) 코드 
        int[] answer = new int[2];
        bool isSuccess = false;
        for(int i = 0; i < nums.Length; i++)
        {
            for(int j = i+1; j < nums.Length; j++)
            {
                if(nums[i] + nums[j] == target)
                {
                    answer[0] = i;
                    answer[1] = j;
                    isSuccess = true;
                    break;
                }
            }

            if(isSuccess) break;
        }

        return answer;
    }
}

 

 

풀이2

문제의 follow up에서 O(N^2) 풀이 말고 생각해볼 수 있는가 묻고 있다. 

그래서 O(N^2)보다 연산량이 적은 풀이를 떠올려봤다. 

 

예전에 배열 문제를 풀때 인덱스를 활용했던 것을 사용해보자. 

배열의 인덱스를 nums의 숫자로 하는 것이다. 

 

 

코드2 - 오답

namespace 배열_구현
{
    internal class LeetCode_Two_Sum
    {
        public int[] TwoSum(int[] nums, int target)
        {
            // indexes 배열 초기화 
             long[] indexes = new long[2000000000];
            Array.Fill(indexes, -1);
            for (long i = 0; i < nums.Length; i++)
            {
                indexes[nums[i] + 1000000000] = i; // -10^9은 인덱스0
            }

            // flags 배열 초기화 
            bool[] flags = new bool[2000000000];

            // 정답 배열 
            int[] answer = new int[2];

            for (long i = 0; i < nums.Length; i++)
            {
                // nums에 nums[i] + (target - nums[i])을 만족하는 nums[j]가 있다면  -> 정답 
                if (flags[target - nums[i] + 1000000000])
                {
                    answer[0] = (int)i;
                    //answer[1] = Array.IndexOf(nums, target - nums[i]);
                     answer[1] = (int)(indexes[target - nums[i] + 1000000000]);
                    break;
                }
                // 없으면 
                else
                {
                    // nums[i] 방문 표시만 하기. 
                    flags[nums[i] + 1000000000] = true;
                }
            }

            return answer;
        }

        static void Main(string[] args)
        {
            LeetCode_Two_Sum p = new LeetCode_Two_Sum();

            int[] nums = { 2, 7, 11, 15 };
            int target = 9;

            foreach(int index in p.TwoSum(nums, target))
            {
                Console.Write($"{index} ");
            }
        }
    }
}

nums[i]의 범위를 생각해서 flags배열과 indexes배열 크기를 크게 잡았는데, 이게 오히려 메모리 초과를 발생시켰다. 

flags배열과 indexes배열을 초기화하는 과정에서 이미 1억을 넘는 연산이 발생해서 시간 초과, 메모리 초과가 발생한 것 같다. 

 

 

풀이3

해설을 보니 이 문제는 해시테이블로 풀어야 좋다고 한다. 

c#에서 Collections안에 HashTable이 있으나 데이터를 Object로 처리해 박싱/언박싱이 발생한다. 

어차피 Hash Table이 키와 값을 사용하는 자료구조이니 Dictionary를 Hash Table처럼 사용하는 것이 더 좋다. 

 

x(=target - cur)라는 키값이 Dictionary에 있으면 dict[x]와 i를 배열로 만들어 반환시키고,

없으면 cur의 인덱스를 Dictionary에 넣으면 된다. (dict[cur] = i)

 

 

코드3 - 정답

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        Dictionary<int, int> dict = new Dictionary<int, int>();

        for(int i = 0; i < nums.Length; i++)
        {
            int cur = nums[i];

            // cur + x = target
            // x = target - cur

            int x = target - cur;
            if(dict.ContainsKey(x))
            {
                return new int[] { dict[x], i };
            }

            dict[cur] = i;
            // dict.Add(cur, i);
        }

        return null;
    }
}

 

 

복습1 풀이 (5/23)

배열에서 두 수의 합이 target을 만족시키는 배열의 인덱스를 반환하는 문제다. 

가장 간단한 방법은 이중 for문을 이용해서 푸는 것이다. 시간복잡도는 O(N^2)이다. 

 

문제 제한사항을 보자. 

• 2 <= nums.Length <= 10^4
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9

nums 배열 최대길이는 10^4 = 10000 = 1만

O(N^2) 풀이로 진행하면 연산 횟수는 10,000 * 10,000 = 100,000,000 = 1억

1억 연산은 1초내로 끝난다. 따라서 O(N^2) 풀이로 풀어도 되겠다. 

 

 

코드1 - 정답

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        for(int i = 0; i < nums.Length; i++)
        {
            for(int j = i+1; j < nums.Length; j++)
            {
                if(nums[i] + nums[j] == target)
                {
                    return new int[2] { i, j };
                }
            }
        }

        return null;
    }
}

 

 

풀이2

nums[i]를 인덱스로 하는 방법을 떠올려 봤다. 

그런데 이 방법은 nums[i] 범위가 너무 커서 integer overflow가 발생한다. 

 

 

풀이3 

이전 코드를 다시 한번 봤다. 

이 문제는 해시 테이블 문제다. Dictionary로 풀 수 있다는 것이다. 

nums[i]와 target - nums[i]의 합이 target인 nums배열의 인덱스를 구해야 한다. 

Dictionary는 key, value를 쌍으로 가지는 자료구조로 ContainsKey메서드로 어떤 key값이 등장했는지 안 했는지 여부를 알 수 있다. 

그러면 이렇게 해보자. 

 

기본적으로 dict에 nums[i], i(인덱스 번호) 를 넣자. 

만약 dict에 target - nums[i] key값이 있으면 { dict[target - nums[i]], i }를 반환한다. 

만약 nums배열을 다 돌았는데도 dict에 target - nums[i]가 없으면 null을 반환한다. (그런데 이 문제에서 답은 반드시 나오므로 null이 반환될리는 없다.)

 

 

코드2 - 정답

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        Dictionary<int, int> dict = new Dictionary<int, int>();
        for(int i = 0; i < nums.Length; i++)
        {
            if(dict.ContainsKey(target - nums[i]))
            {
                return new int[] { dict[target - nums[i]], i };
            }
            dict[nums[i]] = i; 
        }

        return null;
    }
}