[leetcode를 풀어보자] python Two Sums

이런 이중 for문을 풀 때 매번 하는 실수가 있어 그 부분부터 고쳐나가야 한다.

 

처음에 했던 말도 안되는 풀이:

class Solution:
	def twoSum(self, nums: List[int], target: int) -> List[int]:
    	for i in range(len(nums)-1):
        	if nums[i] + nums[i+1] == target:
            	return True

1. 우선 이중 포문을 활용하는 것에 대해 제대로 고려를 못함

2. return 값에 대해서 제대로 고려하지 않음......

 

제대로 된 이중 포문을 이용한 brute force 방법의 풀이는 다음과 같다.

from typing import List
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

 

leetcode의 특징이지만 follow-up 질문들이 사실 메인 질문인 경우가 많다.

사실 hashmap을 사용하지 않은 이중포문의 경우 알고리즘 복잡도가 O(n^2)에 비례하기 때문에 효율이 좋지 못하다. 이를 개선하기 위해서 dictionary 포맷이 필요하다.

 

from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        values = {}
        for idx, value in enumerate(nums):
            if target - value in values:
                return [values[target-value], idx]
            else:
                values[value] = idx