[LeetCode] Two Su

문제 파악

1. 배열 내부에 있는 요소들의 합이 우리가 원하는 target 정보와 일치하는 경우에 해당 인덱스 두 가지를 리턴
2. 제공되는 nums 는 중복되는 숫자가 있을 수 있고, 두 개를 결정한다는 특징이 존재
3. 정답이 될 수 있는 답은 하나

[제약 사항]

10^4 까지 이뤄지기 때문에 O(n^2) 의 경우에는 10^8 까지 이뤄질 수 있어, 위험할 가능성이 있다.

접근 방법

1. O(n^2)의 해결 방법 (완전 탐색)
   중첩 반복문을 활용하여 배열의 각 요소를 돌며, sum이 target과 같은지 확인
2. nlogn의 해결 방법?
   좀 더 개선하는 방법? (nlogn, logn 정도 있을 것 같다.)nlogn은 정렬의 시간 복잡도 → 리스트를 정렬하면 새로운 방식이 보이지 않을까?
   좌, 우에서 차례대로 접근하면서 쓸 수도 있지 않을까?
3. 해시맵을 사용하는 방법?
   해시맵을 통해서 저장하면서 Target을 만드는데 필요한 숫자가 해시맵에 존재하는지 확인하여, O(1)의 시간복잡도로 확인하는 방법 → wow…

코드 구현

O(n^2)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int sum = 0;
        int[] result = new int[2];

        for (int i = 0 ; i < nums.length ; i++) {
            for (int j = 0 ; j < nums.length ; j++ ){
                if (i == j) continue;
                sum = nums[i] + nums[j];
                if(sum == target) {
                    result[0] = i;
                    result[1] = j;
                }
            }
        }
        return result;
    }
}

l, r

import java.util.Arrays;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 정렬을 진행
        Arrays.sort(nums);

        // 좌우 인덱스 설정
        int l = 0, r = nums.length - 1;

        while(l < r) {
            if(nums[l] + nums[r] < target) {l += 1;}
            else if(nums[l] + nums[r] > target) {r -= 1;}
            else {break;}
        }

        return new int[] {l, r};
    }
}

Hashmap

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> memo = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            int needed = target - nums[i];
            if(memo.containsKey(needed)) {
                    return new int[] {memo.get(needed), i};
            }
            memo.put(nums[i], i);
        }
        return new int[] {-1, -1};
    }
}

배우게 된 점

해시맵을 사용하면서 접근하는 방식은 처음으로 알게된 것 같다.

HashMap의 연산

• key-value 쌍 추가하기
• hashtable.put(2022390, "노정호");
• key에 해당하는 value 접근하기
• hashtable.get(2023390); // "노정호"
• key에 해당하는 value 수정하기
• hashtable.replace(2023390, "이승규");
• key-value 쌍 제거
• hashtable.remove(2023390);
• 해당 key가 존재하는지 확인 (containsKey() - 시간복잡도 O(1))
• if (hashtable.containsKey(2023390)) { System.out.println(hashtable.get(2023390)); // 키가 있다면 출력 } else { System.out.println("저장된 키가 없습니다."); }

시간 복잡도를 고려하면서, 접근할 수 있는 방법을 고려하는 방식을 통해서 내가 가진 자료구조 혹은 알고리즘 중 어떤 것으로 구성해볼지 생각하는 사고를 통해서 접근해봐야겠다.