8. String to Integer (atoi)

문제

Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer.

The algorithm for myAtoi(string s) is as follows:

1. Whitespace: Ignore any leading whitespace (" ").
2. Signedness: Determine the sign by checking if the next character is '-' or '+', assuming positivity if neither present.
3. Conversion: Read the integer by skipping leading zeros until a non-digit character is encountered or the end of the string is reached. If no digits were read, then the result is 0.
4. Rounding: If the integer is out of the 32-bit signed integer range [-231, 231 - 1], then round the integer to remain in the range. Specifically, integers less than -231 should be rounded to -231, and integers greater than 231 - 1 should be rounded to 231 - 1.

Return the integer as the final result.

 

Example 1:

Input: s = "42"

Output: 42

Explanation:

The underlined characters are what is read in and the caret is the current reader position.
Step 1: "42" (no characters read because there is no leading whitespace)
         ^
Step 2: "42" (no characters read because there is neither a '-' nor '+')
         ^
Step 3: "42" ("42" is read in)
           ^

Example 2:

Input: s = " -042"

Output: -42

Explanation:

Step 1: "   -042" (leading whitespace is read and ignored)
            ^
Step 2: "   -042" ('-' is read, so the result should be negative)
             ^
Step 3: "   -042" ("042" is read in, leading zeros ignored in the result)
               ^

Example 3:

Input: s = "1337c0d3"

Output: 1337

Explanation:

Step 1: "1337c0d3" (no characters read because there is no leading whitespace)
         ^
Step 2: "1337c0d3" (no characters read because there is neither a '-' nor '+')
         ^
Step 3: "1337c0d3" ("1337" is read in; reading stops because the next character is a non-digit)
             ^

Example 4:

Input: s = "0-1"

Output: 0

Explanation:

Step 1: "0-1" (no characters read because there is no leading whitespace)
         ^
Step 2: "0-1" (no characters read because there is neither a '-' nor '+')
         ^
Step 3: "0-1" ("0" is read in; reading stops because the next character is a non-digit)
          ^

Example 5:

Input: s = "words and 987"

Output: 0

Explanation:

Reading stops at the first non-digit character 'w'.

 

Constraints:

• 0 <= s.length <= 200
• s consists of English letters (lower-case and upper-case), digits (0-9), ' ', '+', '-', and '.'.

 

https://leetcode.com/problems/string-to-integer-atoi

 

풀이

String과 long 2가지 방식으로 풀어보았다.

입력값이 String인 관계로 우선 String으로 구현했는데, 제약조건들을 맞추는데에는 숫자로 바로바로 판단하는게 좋을 것 같다고 생각해서 long으로도 구현해보았다.

 

String 보다는 숫자로 진행하는 것이 속도는 더 빨랐는데, 시간을 더 줄일 수 있는 방법은 아직 못찾았다.

입력값 "   +0 123"에 대해 출력이 0으로 나와야 하는 것으로 보아, 맨 앞 공백만 무시하면 될 것 같아서 split을 통해 공백을 제거한 후 진행해 봤으나 시간 소요가 더 컸다.(7ms)

어차피 확인할텐데 split을 위해 String을 뒤져보는데에 시간 소요가 더 있었던 것으로 보인다.

 

코드

String으로 진행

class Solution {
    public int myAtoi(String s) {
        StringBuilder sb = new StringBuilder();
		int res = 0;
		char[] signed = new char[] {' '};
		
		for(char c : s.toCharArray()) {
			if(c == ' ') {
				if(sb.length() != 0 || signed[0] != ' ') {
					break;
				}
				continue;
			}
			if(c == '-' || c == '+') {
				if(sb.length() != 0 || signed[0] != ' ') {
					break;
				}
				signed[0] = c;
				continue;
			}
			if(Character.isDigit(c)) {
				sb.append(c);
			} else {
				break;
			}
		}
		
		if(sb.length() != 0) {
			try {		
				res = (signed[0] == '-')? Integer.parseInt(sb.toString()) * -1 : Integer.parseInt(sb.toString());
			} catch(NumberFormatException e) {
				res = (signed[0] == '-')? Integer.MIN_VALUE : Integer.MAX_VALUE;
			}
		}
		
        return res;
    }
}

 

숫자로 진행

class Solution {
    public int myAtoi(String s) {
        String input = s.trim();
		int idx = 0;
		int signed = 1;
		long res = 0;
		
		if(input.isEmpty()) {
			return 0;
		}
		
		if(input.charAt(idx) == '-' || input.charAt(idx) == '+') {
			signed = (input.charAt(idx++) == '-')? -1 : 1;
		}
		
		while(idx < input.length() && Character.isDigit(input.charAt(idx))) {
			res = (res * 10) + Character.getNumericValue(input.charAt(idx++));
			if(res > Integer.MAX_VALUE) {
				return (signed == -1)? Integer.MIN_VALUE : Integer.MAX_VALUE;
			}
		}
				
        return (int) res * signed;
    }
}

결과

String 진행 : runtime 3ms, memory 42.88MB

숫자로 진행 : runtime 2ms / memory 42.36MB