[리트코드] 14일차

1. Two Sum

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] answer = new int[2];
        for (int i = 0 ; i< nums.length; i++){
            for (int j = i+1; j < nums.length; j++){
                if (nums[i] + nums[j] == target){
                    answer[0] = i;
                    answer[1] = j;
                    break;
                }
            }
            if (answer[1] != 0) break;
        }

        return answer;
    }
}

일단 이렇게 풀었지만.. 이건 너무 오래 걸린다.

해시맵을 사용해봐야하나? 조금 더 생각해봐야겠다.

처음에는 모든 걸 해시맵에 넣고 (<숫자, 인덱스>) 찾으면 된다고 생각했는데, 막상 해보니 [3,3] 의 경우에 찾을 수 없다는 것을 알게되었다. 즉 중복되는 값에 대해서는 해결하기 어렵다. 리스트 형식으로 인덱스를 저장하는 것도 딱히..

답안을 보니 접근 자체는 잘했다고 생각했다. 그런데 굳이 다 넣을 필요가없고 앞선 것에서 있는지만 확인하는 걸로 위의 반례를 처리할 수 있었다.

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

 

202. Happy Number

class Solution {
    public boolean isHappy(int n) {
        int temp = n;
        while (temp > 4){
            int nextTemp = 0;
            while (temp > 0){
                int d = temp % 10;
                nextTemp += d*d;
                temp /= 10;
            }
            temp = nextTemp;
        }
        if (temp == 1){
            return true;
        }
        return false;
    }
}

처음에 이렇게 접근 했는데.. 뭔가 억지 부려서 푼 느낌이 난다.. 

답안을 보니 해시맵을 통해서 간단하게 루프를 확인할 수 있는 방법이 있었다.

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> visit = new HashSet<>();
        
        while (!visit.contains(n)) {
            visit.add(n);
            n = getNextNumber(n);
            if (n == 1) {
                return true;
            }
        }
        
        return false;
    }

    private int getNextNumber(int n) {
        int output = 0;
        
        while (n > 0) {
            int digit = n % 10;
            output += digit * digit;
            n = n / 10;
        }
        
        return output;
    }
}

해시맵에 이미 존재하는 경우에는 이미 한번 계산했던 만큼 다시 루프가 돈다는 의미로 해결했던데 꽤나 흥미로웠다.

 

219. Contains Duplicate II

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashMap<Integer, Integer> numIdx = new HashMap<>();

        for (int i = 0; i<nums.length; i++){
            if (numIdx.containsKey(nums[i])){
                if (i - numIdx.get(nums[i]) <= k){
                    return true;
                }
            }
            numIdx.put(nums[i], i);
        }
        return false;
    }
}

위의 문제와 비슷해서 간단하게 해결했다.

 

128. Longest Consecutive Sequence

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums){
            numSet.add(num);
        }

        int longest = 0;

        for (int num : numSet){
            if (!numSet.contains(num - 1)){
                int length = 1;

                while (numSet.contains(num + length)) {
                    length++;
                }

                longest = Math.max(longest, length);
            }
        }

        return longest;
    }
}

도저히 답이 생각이 안나서 해결답안을 봤다. 

제일 어려웠던 건 위로 가야할지 아래로 가야할지 정하는 게 어려웠다. 그런데 코드를 보니 예외사항이 안 생기게 한쪽으로 계산하게 만들면 되는 거였다는 것을 알게되었다. 

완료!