1. Two Sum + 9. Palindrome Number

1. Two Sum

문제

인풋으로 받은 integer list에서 더하면 target이 되는 두 개 숫자의 list index를 반환하는 문제

내가 푼 방법

문제를 보자마자 target - list[i] = list[j] 라는 아이디어가 떠올랐다. 그러면 답은 i, j 겠지?
이후로 시간 복잡도를 더 줄일 수 있는 아이디어가 생각나지 않아 무식하게 brute force 방법으로 풀었다. 결과는 N^2

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

더 빠르게 푼 사람들

나는 중간쯤에 위치하고 있어서 빠르게 푼 사람들의 답안을 슬쩍보고 HashMap을 사용하면 된다는 사실을 발견했다!
target - list[i] = list[j] 라는 것도 알았으면서 왜 HashMap 쓸 생각을 못했을까? HashMap 을 쓰면 시간복잡도는 2N 으로 확 줄어든다.

class Solution {
	public int[] twoSum(int[] nums, int target) {
		// find -> target - int[i] = int[j]
		Map<Integer, Integer> map = new HashMap<>();
		for (int i=0; i<nums.length; i++) {
			map.put(nums[i], i);
		}
		for (int i=0; i<nums.length; i++) {
			int diff = target - nums[i];
			if (map.containsKey(diff) && map.get(diff) != i) {
				return new int[]{i, map.get(diff)};
			}
		}
		return new int[]{-1, -1};
	}
}

9. Palindrome Number

문제

인풋으로 받은 integer가 palindrome인지 판단하는 문제. 숫자를 string으로 변환하지않고 풀어보라는 코멘트가 있다.

내가 푼 방법

고민하다 10으로 계속 나누면 각 자릿수를 얻을 수 있다는 아이디어가 떠올랐다.

1. 몫을 계속 10으로 나누면 나머지가 자릿수
2. 자릿수를 배열에 순서대로 넣는다
3. 양 끝의 숫자를 비교한다

class Solution {
    public boolean isPalindrome(int x) {
        if (x<0) {
            return false;
        }
        // %10 remainder
        List<Integer> list = new ArrayList<>();
        while (x>0) {
            list.add(x%10);
            x = x/10;
        }
        int size = list.size()/2;
        for (int i=0; i<size; i++) {
            if (list.get(i) != list.get(list.size()-1-i)) {
                return false;
            }
        }
        return true;
    }
}

더 빠르게 푼 사람들

나보다 더 빠른 답을 보니 한가지 아이디어가 더 필요했다. 양 끝의 숫자를 비교할 필요 없이 뒤집은 수를 만들어내면 된다는 점!
각 자릿수를 비교하는 로직이 제거되기 때문에 더 빠르다.

class Solution {
    public boolean isPalindrome(int x) {
        if (x<0) {
            return false;
        }
        // %10 remainder
        int result = x;
        int c = 0;
        while (x>0) {
            c = c*10+x%10;
            x = x/10;
        }
        if (c == result) {
            return true;
        }
        return false;
    }
}

여기서 palindrome 판단이니 절반까지만 확인하자는 아이디어까지 추가하면 더 빨라진다.

class Solution {
    public boolean isPalindrome(int x) {
        // 10, 100 등의 숫자는 계속 0이 나오므로 제외해야 한다.
        if (x<0||x%10==0&&x!=0) {
            return false;
        }
        // %10 remainder
        int c = 0;
        // c가 더 커질 때 멈춰야 한다.
        // 중앙 숫자가 c의 끝자리로 들어가야하기 때문
        while (x>c) {
            c = c*10+x%10;
            x = x/10;
        }
        if (c == x) {
            return true;
        }
        // 자릿수가 홀수인 경우 중앙 숫자는 제거해버리면 된다.
        if (c/10 == x) { 
            return true;
        }
        return false;
    }
}

절반까지만 확인하는 아이디어는 진짜 혁신이라는 생각이 들었다. 어떻게 하면 저런 생각이 뿅 튀어나오는걸까?