two sum

leetcode.com/problems/two-sum/

Two Sum - LeetCode

 

언제든 이직할 수 있도록 코딩테스트 연습하려고 leetcode에 가입했다

그냥 제일 상위에 있는 문제 중 easy 난이도 하나를 골라서 풀었는데

한번에 통과는 했지만 많은 반성을 하게 됐다...

내 답은 이렇게 적었는데

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        results = []
        for i, first in enumerate(nums):
            for j, second in enumerate(nums):
                if i == j:
                    continue
                
                if target == first + second:
                    return [i, j]
                

 

답지를 보고 나니 너무 부끄러운 코드다...

진짜 생각없이 brute force로 풀었는데

One/Two-pass Hash Table 답을 보면 참 현타 오는 코드다 ㅋㅋ

// Two-pass Hash Table
public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], i);
    }
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement) && map.get(complement) != i) {
            return new int[] { i, map.get(complement) };
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

// One-pass Hash Table
public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

                

혼자서 + 대충 일하던 습관이 그냥 몸에 베어버린 2중 for문...

O(n)으로 풀 수 있는 답은 보니 내 O(n^2)은 완전 쓰레기가 되어렸다

이건 알고리즘 문제니깐 좀 더 최적화 포인트를 생각해볼 수 있었는데

많은 반성 포인트만을 남겨둔채 일단 통과... ㅋㅋㅋ

 

매일까진 아니라도 최소한 일주일에 한문제는 풀어봐야겠다

진짜 감 많이 잃었네...