[리트코드] 1. Two Sum

문제

https://leetcode.com/problems/two-sum/

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]

 

Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

 

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

 

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

 

Constraints:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

접근 방법

아이디어

문제에서 오직 1가지 답만 존재한다고 했기에 중복 정답은 존재하지 않는다. 모든 경우를 조사해야 하므로 반복문 또는 재귀를 사용해서 문제를 해결한다.

 

방법

완전 탐색 → 버겁긴 하다 → 추후 최적화 필요

• 반복문
• 재귀

코드 구현

1. 반복문

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++){
                // 선택된 두 정수의 합이 target이면 두 인덱스를 반환한다
                if (nums[i] + nums[j] == target) {
                    return new int[] {i,j};
                }
            }
        }
        return new int[] {};
    }
}

•시간 복잡도: O(N²)

•실행 시간 (Runtime): 44ms

•메모리 사용량 (Memory): 44.94MB

 

2. 재귀(백트래킹)

class Solution {
     public int[] twoSum(int[] nums, int target) {
        return backtracking(nums, target, 0, new ArrayList<Integer>());
    }

    public int[] backtracking(int[] nums, int target, int start, ArrayList<Integer> ans) {
        // base case: ans에 원소가 2개가 들어가 있다면,
        if (ans.size() == 2) {
            // 두 원소의 합이 target이면 ans를 반환하고, 그렇지 않으면 null을 반환한다
            if (nums[ans.get(0)] + nums[ans.get(1)] == target) {
                return new int[]{ans.get(0), ans.get(1)};
            }
            return null;
        }

        // 인덱스 0부터 끝까지 순회한다
        for(int i = start; i < nums.length; i++) {
            // ans에 인덱스 i를 추가한다.
            ans.add(i);
            // 재귀 함수를 호출한다.
            int[] result = backtracking(nums, target, i+1, ans);
            // 반환값이 존재하면 그 반환값을 반환한다.
            if (result != null) {
                return result;
            }
            // 반환값이 false이면 ans에서 해당 인덱스를 제거한다.
            ans.remove(ans.size() - 1);
        }
        
        return null;
    }
}

• 시간 복잡도: O(N²)

• 실행 시간 (Runtime): 578ms

• 메모리 사용량 (Memory): 45.43MB

 

회고

기본이되는 완전 탐색 문제를 반복문과 재귀를 통해 풀어보았다. 아직 백트래킹 개념이 머릿속에 자연스럽게 떠오르지 않지만, 비슷한 유형의 문제를 풀면서 익숙해져야겠다. 현재 두 방법 모두 통과는 되었지만 최적화가 필요한 상황이다. 다음에 이어서 최적화 작업을 진행해야겠다!