본문 바로가기

Study/Algorithm

[알고리즘의 R자도 모르는 개발자의 알고리즘 풀이] - 1. Array - Two Sum

[알고리즘의 R자도 모르는 개발자의 알고리즘 풀이] - 1. Array - Two Sum

LeetCode의 Array 문제 중 Two Sum을 직접 풀어보고 가장 모범 답안인 풀이를 분석해봤다. 

 

🗝 풀어볼 알고리즘


Tech Interview Handbook

 

Tech Interview Handbook

Carefully curated content to help you ace your next technical interview

yangshun.github.io

Two Sum - LeetCode

 

Two Sum - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

 



<문제>

배열 하나가 주어진다. 그 배열의 두 인덱스를 return 해주면 되는데 그 인덱스의 값을 더했을 때 target이 나와야 한다.

각각의 Input은 한 정답만 가지고 있으며 한 element를 두 번 사용해서는 안 된다.

 

<내가 생각한 접근 방식>

1. for문 두 개 돌려서 하나씩 체크해보면 되지 않을까?

class Solution {
        public int[] twoSum(int[] nums, int target) {
            for (int i = 0; i < nums.length; i++) {
                for (int j = 0; j < nums.length; j++) {
                    if (target == nums[i] + nums[j]) {
                        return new int[]{i, j};
                    }
                }
            }
            return null;
        }
    }

 

이렇게 생각했는데 생각해 보니 필요없는 루프가 생긴다.

바로 [0]에서 [1]로 갔을 때 두 번째 for 구문에서 다시 0부터 체크한다.

비교해야 하는 순서를 정리해보니 두 번째 for문에서는 시작값이 i+1이 되면 이런 중복은 피할 수 있다는 것을 알았다.

 

 

말로 어떻게 표현 해야 할지 몰라서 손을 빌렸다...

 

2. 두 번째 for문의 j 시작값을 i + 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++) {
                    return new int[]{i,j};
                }
            }
            return null;
        }
    }

 

3. if문을 통해 결과 값을 체크하는 구문을 넣어주고 리턴한다. 

    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++) {
                    if (target == nums[i] + nums[j]) {
                        return new int[]{i, j};
                    }
                }
            }
            return null;
        }
    }

 

 

 

📖 WIL


다 풀고 나서 Solution을 보는데 다른 사람들은 정답이 없을 때 throw exeption으로 핸들링 해준 것을 볼 수 있었다.

  throw new IllegalArgumentException("No two sum solution");

나도 풀이 마지막까지 이런 꼼꼼함이 있으면 더 좋을 것 같다.

 

LeetCode에는 각 Solution마다 Time complexity와 Space complexity에 대해 부연 설명이 있었다.

내가 작성한 풀이는 'Brute Force'에 해당 하는 접근 방법이었는데 답안으로 제시된 3가지 알고리즘 중에서 시간복잡도가 가장 높았다.

시간 복잡도가 가장 낮은 알고리즘 풀이는 'One-pass HashTable'이다.

 

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) { //제시된 array num의 length만큼 1씩 증가하며 loop
        int complement = target - nums[i]; //num[i]에 해당하는 값이 필요한 다른 숫자(i와 함께 값이 될 index) 
        if (map.containsKey(complement)) { // map에 그 값이 있는지 key로 확인
            return new int[] { map.get(complement), i }; //있다면 더 돌지 않고 바로 정답을 리턴해준다
        }
        map.put(nums[i], i); //map에 인덱스와 값을 검색한다
    }
    throw new IllegalArgumentException("No two sum solution");
}

 

내 풀이방법을 제외한 나머지 두 가지 풀이 방법은 모두 Hash Table을 이용한 풀이 방법이었는데

말 그대로 'Brute Force'로 해결한 나 자신이 쪼금은 부끄러웠다. (쪼금만 부끄러운 이유는 모르는 걸 이제는 배웠으니까... (당당))
왠지 비기너 레벨에서는 HashTable을 이용해서 풀 수 있는 문제들이 많이 나올 것 같다.

내 정답보다 제시해 준 솔루션에서 제일 좋은 접근 방법을 내 것으로 만드는 과정이 더 재미있었던 것 같다.