[Grind75-LeetCode] String to Integer (atoi) JAVA

반응형

728x90

[Grind75-LeetCode] String to Integer - Medium

---

접근

• 구현

---

풀이

문자열을 정수로 변환하는 atoi 함수를 구현하는 문제이다. atoi는 C언어에 존재하는 ASCII to Integer로 문자열을 정수로 변환하는 자바의 parseInt와 같은 메서드이다. 기본적인 atoi 함수는 주어진 문자열을 정수로 변환하고 변환이 불가능한 경우 0을 반환한다. 그리고 범위 체크 부분이 존재하지 않기 때문에 범위를 벗어난 값이 들어오게 되면 의도치 않은 값이 반환되기도 한다. 반면 자바의 parseInt의 경우 똑같이 문자열을 정수로 변환하는 함수이지만 변환이 불가능한 경우 런타임 예외인 NumberFormatException를 던지게 되고 정수로 변환 가능한 범위인지도 체크하기 때문에 범위를 벗어난 경우에도 NumberFormatException 예외를 던지게 된다. 런타임 예외가 발생하는 만큼 사용자가 예외 처리를 섬세하게 해야 하지만 잘못된 값을 가진채 다음 작업으로 넘어가 더 큰 문제가 발생하는 건 막을 수 있다. 

 

이번 문제는 C언어의 atoi를 자바의 parseInt처럼 범위 처리등 추가 기능을 가진 atoi로 구현하는 문제이다. 처리 과정은 4 단계로 이루어져 있으며 공백 처리, 부호 처리, 숫자 변환, 범위 처리로 진행된다. 자세한 설명은 코드와 함께 진행하겠다. 문제 자체는 어려운 부분이 없으나 생각하지 못한 예외가 많아 제출을 많이 했던 문제다.

    public int myAtoi(String s) {
        //1. 공백 처리
        s = s.trim();
        if (s.isEmpty()) {
            return 0;
        }

처리 과정을 쉽게 구분하기 위해 주석을 달았다. 첫 번째 처리로 공백 처리이다. 공백 처리는 입력으로 주어진 문자열 s의 앞부분 공백을 제거하는 처리이다. 구현해야 할 atoi 함수는 문자열 앞부분 공백은 무시하고 숫자나 문자를 만나는 순간 처리를 시작하기 때문에 trim을 사용해 제거해 주었다. 그리고 빈 문자열인 경우 변환이 불가능하여 0을 반환해 주었다.

	//2. 부호 처리
        int sign = 1;
        int start = 0;

        if (s.charAt(0) == '-') {
            sign = -1;
            start = 1;
        } else if (s.charAt(0) == '+') {
            start = 1;
        }

다음은 부호 처리이다. 부호의 경우 문자열의 앞 공백을 무시하고 제일 처음 나오는 경우에만 부호로 인정한다. 숫자가 나오기 전 맨 처음으로 오는 +, - 만 부호로 인정하기 때문에 공백을 제거한 문자열의 첫 문자가 -인 경우 sign 변수를 -1로 만들어 준다. 예제에는 - 부호만 나와 양수일 경우 부호가 없는 숫자를 양수로 치는 줄 알았으나 + 부호는 생략이 가능한 거였다. 그렇기 때문에 각 부호가 나오게 되면 숫자 변환 시작을 두 번째 문자부터 진행해야 하기에 start 값을 증가시켜 준다.

	//3. 숫자 변환
        long res = 0;

        for (int i = start; i < s.length(); i++) {
            char c = s.charAt(i);

            if (Character.isDigit(c)) {
                res = res * 10 + (c - '0');

                // 범위 초과 체크
                if (res > Integer.MAX_VALUE) {
                    return (sign == 1) ? Integer.MAX_VALUE : Integer.MIN_VALUE;
                }
            } else {
                break;
            }
        }
        
        res *= sign;

다음은 숫자로 변환하는 부분이다. 부호를 지난 뒤 나오는 문자를 숫자로 변환하게 되는데 변환을 진행하다 숫자가 아닌 문자를 만나게 되면 거기서 변환을 중지하게 된다. 예제의 "1337c0d3"이라는 문자열이 있을 때 1337을 변환하고 숫자가 아닌 문자 c를 만나며 변환이 종료되어 결과로 1337을 반환하게 된다. 여기서 주의해야 할 문제는 범위이다. 숫자 변환 파트에 범위 체크 부분이 섞여있는데 처음엔 StringBuilder를 사용해 문자가 나오기 전까지의 숫자를 모아둔 뒤 범위체크를 따로 진행했었다. 그런데 이 문제의 문자열 s의 최대 길이는 200으로 200자리가 모두 숫자라면 말도 안 되게 큰 값이 만들어지게 되는 것이다. 거기서 정수형의 범위인 21억 즉 10자리에서 끊어서 체크를 한다 해도 000005 같이 앞에 0이 많이 들어있는 경우 자릿수는 6자리지만 실제 값은 5로 정확한 체크가 불가능했다. 그렇다고 BigInteger를 사용하니 성능도 떨어지고 코드도 복잡해졌다. 그래서 숫자를 한 개 처리할 때마다 범위 체크도 같이 진행해 주었다. 정수형의 범위를 벗어나는 경우 sign 변수의 부호를 따라 각각 반환을 해주었다. 변환을 진행할 때는 long 타입을 사용해 오버플로우를 피해 주어야 한다. 변환이 완료되면 최종 변환된 값이 부호를 적용해 준다. 

        //4. 범위 처리
        if (res > Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        } else if (res < Integer.MIN_VALUE) {
            return Integer.MIN_VALUE;
        }

        return (int) res;
    }

나머지 범위 처리 부분이다. 마지막 반복 수행이 지난 다음 범위 체크는 되지 않은 상태이기 때문에 최종 범위 체크를 수행해주고 결과를 반환한다. 

기본

 

BigInteger를 사용한 코드는 6ms의 실행 시간을 가졌었는데 뒤에 전체 코드 부분에 BigInteger 사용 코드도 첨부하겠다.

---

전체 코드

기본 코드

class Solution {
    public int myAtoi(String s) {
        //1. 공백 처리
        s = s.trim();
        if (s.isEmpty()) {
            return 0;
        }

        //2. 부호 처리
        int sign = 1;
        int start = 0;

        if (s.charAt(0) == '-') {
            sign = -1;
            start = 1;
        } else if (s.charAt(0) == '+') {
            start = 1;
        }

        //3. 숫자 변환
        long res = 0;

        for (int i = start; i < s.length(); i++) {
            char c = s.charAt(i);

            if (Character.isDigit(c)) {
                res = res * 10 + (c - '0');

                // 범위 초과 체크
                if (res > Integer.MAX_VALUE) {
                    return (sign == 1) ? Integer.MAX_VALUE : Integer.MIN_VALUE;
                }
            } else {
                break;
            }
        }

        res *= sign;

        //4. 범위 처리
        if (res > Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        } else if (res < Integer.MIN_VALUE) {
            return Integer.MIN_VALUE;
        }

        return (int) res;
    }
}

 

BigInteger

	//3. 숫자 변환
        StringBuilder sb = new StringBuilder();

        for (int i = start; i < s.length(); i++) {
            char c = s.charAt(i);

            if (Character.isDigit(c)) {
                sb.append(c);
            } else {
                break;
            }
        }

        if (sb.isEmpty()) {
            return 0;
        }

        //4. 범위 처리
        BigInteger res = new BigInteger(sb.toString());
        res = res.multiply(new BigInteger(Integer.toString(sign)));

        if (res.compareTo(new BigInteger(String.valueOf(Integer.MAX_VALUE))) >= 0) {
            return Integer.MAX_VALUE;
        } else if (res.compareTo(new BigInteger(String.valueOf(Integer.MIN_VALUE))) <= 0) {
            return Integer.MIN_VALUE;
        } else {
            return res.intValue();
        }