Today's Algorithm(2018-11-09)

leetcode 8. String to Integer (atoi)

atoi메서드를 실제 구현해보는 문제인데요. 이 문제 푸는데 얘 먹었습니다. 이게 특정 방식으로 풀지 않으면 갈수록 미궁 속이 되더라구요. 결국은 다른 사람의 코드를 참고하여 해결하였습니다. 문제 풀면서 힘들었던 점과 참고한 풀이에서는 어떻게 해결했는지 살펴볼게요.

막혔던 부분

• Integer 범위 넘어가는 수 처리

  • 전 처음에 문자열을 가지고 이를 처리하려 했습니다. Integer.parseInt()를 너무 좋아했던거죠. 그렇다보니 넘어가는 수에 대해 자리수 계산하고 그랬습니다. 정확하지도 않고 그게 맞는지도 모르는채 말이죠.
  • 하지만 각각의 자리 수에 대해서 바로바로 Integer형으로 만든 다음 long형인 sum에 기존 sum에 10을 곱하고 그 수를 더하면 바로바로 그 실제값을 알 수 있기 때문에 위 문제를 해결할 수 있습니다. Integer.MAX_VALUE나 Integer.MIN_VALUE 비교만 하면 되는 것이죠.

• 수 앞에 000000000123와 같이 많은 개수의 0 처리

  • 이 문제 또한 바로바로 Integer형으로 만든다음 sum에 더하면 해결할 수 있습니다. 기존 수가 0이라면 0에다가 10 곱해도 안 증가하고, 0을 더해도 안 증가하기 때문입니다.

• 수 앞뒤의 부호처리

  • 이 문제에서 이상한 점이 있다면 부호의 위치였습니다. -5-는 -5로 인식하고 -+2는 잘못되어 0으로 인식하고, 0-1은 0으로 인식하여야 통과할 수 있는데 전 이게 무슨 규칙이 있는건지 잘 모르겠더라구요.
  • 다른 사람의 풀이를 보면서 확실히 감을 잡을 수 있었습니다. 우선 맨 처음에 부호가 진짜 부호이고 맨 처음에 부호가 없고 수가 나오다가 부호가 갑자기 나오면 오류 처리되어 0을 반환해야 한다는 점입니다. 또 부호가 나온 다음 다른 부호가 나오면 그 이전까지의 값을 반환하거나 0을 반환해야 하는 것이었습니다. 이런 부호처리 규칙을 깨닫지 못해 처음 코드를 작성할 때 조건문을 엄청 많이 썼거든요...
  • 부호처리 부분 때문에 start 라는 지역변수를 두어 부호가 있고 없음에 따라 다르게 처리될 수 있도록 시작위치의 인덱스를 지역변수로 두어 처리하였습니다.
  • 그리고 sum은 인덱스가 부호 이후에 시작하기 때문에 부호의 경우 int값으로 +, -에 따라 +1, -1로 부여하였고, 나중에 이 부호값을 곱하여 반환하도록 하였습니다.

class Solution {
    public int myAtoi(String str) {
        if (str.isEmpty() || str.trim().length() == 0) {
            return 0;
        }

        String newStr = str.trim();
        int len = newStr.length();
        int start = 0;
        int sign = 1;
        long sum = 0;
        if (newStr.charAt(0) == '+') {
            sign = 1;
            start++;
        }
        else if (newStr.charAt(0) == '-') {
            sign = -1;
            start++;
        }

        for (int i = start; i < len; i++) {
            if (!Character.isDigit(newStr.charAt(i))) return (int) sum * sign;
            sum = (sum * 10) + (newStr.charAt(i) - '0');
            if (sum * sign > Integer.MAX_VALUE) return Integer.MAX_VALUE;
            if (sum * sign < Integer.MIN_VALUE) return Integer.MIN_VALUE;
        }

        return (int) sum * sign;
    }
}

이번 문제에서 가장 걸림돌은 역시 문자열을 숫자로 변환하지 않은 점과 문제를 제대로 이해하지 못했다는 점입니다. 영어로 되어있어 제가 문제에서 미처 못 봤는지 모르겠지만 혼자 힘으로 해결하지 못해 다소 아쉽네요.

 

 

leetcode 9. Palindrome Number

이 문제는 난이도도 easy이고 실제 구현할 코드도 되게 짧아서 비교적 쉽게 풀었는데요. 다른 사람의 풀이를 보다가 재미있는 코드를 보아서 기록해두려 합니다. 회문에서 저와 같이 문자열로 만든 다음에 char타입으로 비교하면 쉽게 풀 수 있는데요. 그런데 String으로 변환하는 과정이 시간이 좀 걸리는 것 같아요.

class Solution {
    public boolean isPalindrome(int x) {
        if(x < 0) return false;
        String str = String.valueOf(x);
        int len = (str.length() - 1) / 2;

        for (int i = 0; i <= len; i++) {
            if (str.charAt(i) != str.charAt(str.length() - 1 - i)) {
                return false;
            }
        }
        return true;
    }
}

그래서 상위권 코드를 보니 String으로 바꾸지 않고 주어진 Integer타입을 활용하여 비교하더라구요. 제가 재미있게 본 코드는 두 자리수 이상일 때 반복문을 돌면서 일의 자리 수를 한 자리씩 쌓아올리고(이전 값에 *10하고 지금값을 더하는 것을 말함) 일의 자리수를 10으로 나누어 밀어버립니다. 그리고 제일 마지막에 반환할 때 쌓아올린 값과 x에서 제일 뒤 한자리 뺀 것과 비교하는 것입니다.(물론 0이상 수일때 반복문 돌리고 마지막에 쌓아올린 값과 x값 그대로 비교해도 됩니다)

public class Solution2 {
    public boolean isPalindrome(int x) {
        if (x < 0) return false;
        int temp = x;
        int sum = 0;
        while (temp > 9) {
            sum = (sum * 10) + (temp % 10);
            temp /= 10;
        }
        return sum == (x / 10);
    }
}

Integer 타입으로 문제해결하려면 좀 더 도전적이고 재미있네요!!