LeetCode [1]: Two Sum

📌 LeetCode [1]: Two Sum

🔗 문제 링크

---

문제 설명 📄

정수 배열 nums와 정수 target이 주어질 때, 두 숫자의 합이 target이 되는 두 숫자의 인덱스를 찾는 문제입니다.
같은 숫자를 두 번 사용할 수 없으며, 유일한 정답이 있다고 가정합니다.

---

문제 접근 방식 📋

처음에는 브루트 포스 방식으로 접근하여, 이중 루프를 사용해 가능한 모든 조합을 확인했습니다. 하지만 이 방식은 시간 복잡도가 O(n^2)이기 때문에, 더 효율적인 방법이 필요했습니다.

아이디어 설명 💡

1. 브루트 포스 방식: 모든 가능한 두 숫자의 조합을 확인하여 nums[i] + nums[j] == target이 되는 경우를 찾았습니다. 이 방식은 간단하지만, 시간 복잡도가 O(n^2)으로 비효율적입니다.

---

Solution 💻 (브루트 포스 방식)

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

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(n^2)
  • 이중 루프를 사용하여 모든 가능한 두 숫자의 조합을 확인합니다.
• 공간 복잡도: O(1)
  • 추가적인 데이터 구조를 사용하지 않으므로 상수 공간만 필요합니다.

---

리팩토링 🛠️ (딕셔너리를 사용한 방식)

개선된 코드

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

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(n)
  • 한 번의 반복문을 사용하여 각 숫자를 딕셔너리에 저장하고, 필요한 값을 찾기 때문에 선형 시간 복잡도입니다.
• 공간 복잡도: O(n)
  • 딕셔너리에 최대 n개의 요소를 저장합니다.

---

코드 설명 📋

1. 딕셔너리를 사용하여 더 효율적으로 문제를 해결했습니다.
2. target - v의 값이 이미 딕셔너리에 존재하는지 확인합니다.
   • 존재하면 두 숫자의 인덱스를 반환합니다.
   • 존재하지 않으면 현재 숫자를 딕셔너리에 저장합니다.
3. 이 방식은 O(n^2)에서 O(n)으로 시간 복잡도를 개선합니다.