.leetCode(1. Two Sum)

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

 

2. 2022.01.03 시도

소요시간: 34분(27분 실패, 7분 구상 및 코딩, n^2복잡도), 5분(map이용)

// n^2
class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int x=0; x<nums.length; x++) {
            int diff = target - nums[x];
            for (int y=x+1; y<nums.length; y++) {
                if (diff == nums[y]) {
                    int[] ret = new int[2];
                    ret[0]=x;
                    ret[1]=y;
                    return ret;
                }
            }
        }
        return new int[2];
    }
}

// map이용
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> indexMap = new HashMap<>();
        for (int x=0; x<nums.length; x++) {
            indexMap.put(nums[x], x);
        }
        
        for (int x=0; x<nums.length; x++) {
            int diff = target - nums[x];
            if (indexMap.containsKey(diff)) {
                int index = indexMap.get(diff);
                if (index == x) {
                    continue;
                }
                
                int[] ret = new int[2];
                ret[0] = x;
                ret[1] = index;
                return ret;
            }
        }
        return new int[2];
    }
}

풀이 접근 과정

exactly one solution 해는 하나만 찾으면 되는구나 싶었다. 꽤나 쉬운 문제처럼 보였다. 이게 화근이였다. 만만하게 보다가 너무 쉽게만 생각해서 일을 그르쳤다. 

들어오는 거 정렬이 안되어있어서 정렬을 따로 해줄까 아니면 그대로 사용할까 했다. 요소를 리턴해야하므로 정렬하면 요소위치가 변해서 그렇게 푸는건 아니라고 생각했다.

set으로 처음에 접근했다가 [3.3]과 같은 예시를 생각해내지 못하고 오답을 내었다.
그러다가 그냥 제일 쉽게 일단 풀어보자고 생각했다. 그리고 풀었다.

set에 생각이 갇혀있었는데 map으로 해도 되겠다. 싶어서 map으로 접근해서 푸니 쉽게 풀렸다.

 

느낀점

• O(n^2)는 최적의 수가 아니었기때문에 구상을 멈췄던 것인데 일단 구상시간이 5분이상 넘어가면 최적값이 아니더라도 풀어봐야겠다는 생각이 들었다.
• 요소의 위치를 리턴할 때는 정렬과 같은 옵션은 배제하는게 좋겠다.
• 제한이 있어서 제한을 이용해보려고 했는데 메모리 제한에 걸렸다. 실제로 문제에는 메모리 제한이 없어 보였는데 말이다. 만약에 메모리 제한이 없다면 O(n)까지도 가능하겠다.

//Memory Limit Exceeded
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] rooms = new int[2_000_000_001];
        int standard = 1_000_000_000;
        
        for (int x=0; x<nums.length; x++) {
            rooms[nums[x]+standard]++;
        }
        
        int[] ret = new int[2];
        int diff =0;
        for (int x=0; x<nums.length; x++) {
            diff = target - nums[x];
            if (rooms[diff+standard] == 2) {
                ret[0]=x;
                break;
            }

            if (rooms[diff+standard] == 1) {
                if (nums[x] == diff) {
                    continue;
                }
                ret[0]=x;
                break;
            }
        }
        
        
        for (int x=ret[0]+1; x<nums.length; x++) {
            if (diff == nums[x]) {
                ret[1] = x;
                break;
            }
        }
        
        return ret;
    }
}

• 부끄럽지만 그래도 첫시도보단 빨리 풀었다. 첫 시도에서는 문제 이해를 잘못한 부분이 많았는데 이번에 그러지 않았다. 하지만 이번에도 처음에 Brute Force방식으로 풀고 말았다. 다음에는 세련된 풀이를 먼저 생각해내면 좋겠다.
• map을 이용해도 더 깔끔하게 풀 수 있다. 코드 정리도 한번 더 할 수 있는지 고민해보면 좋겠다.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> tempMap = new HashMap<>();
        for (int x=0; x<nums.length; x++) {
           if (tempMap.containsKey(nums[x])) {
               return new int[]{x, tempMap.get(nums[x])};
           }

           tempMap.put(target-nums[x], x);
        }
        
        return null;
    }
}

 

 

1. 2021.01.09 시도

소요시간: 37분

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

        return null;
    }
}

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

        return null;
    }
}

풀이 접근 과정

(문제를 잘못 이해하고 한 생각..) 작은 수면 빼고 recursive하면되겠다.
(문제를 잘못 이해하고 한 생각..) 매소드 만들어서 인덱스도 하나 더 넣어주어야겠다.
(문제를 잘못 이해하고 한 생각..) 리턴을 만들어주는게 어렵다.. 전역변수 안쓰고
문제를 잘못이해햇다. 여러개 갯수제한 없이 더해서 target을 구해주는건 줄로 오해했다. 문제 제목처럼 2개만 더하는건데 하고 바로 풀었다.

 

느낀점

1. 문제를 또 오해했다.
2. 두개만 더하면 되니 for문 2번으로 바로 풀 수 있었다. hashMap으로 데이터 저장해서 푼 풀이도 잇다.

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형