[알고리즘] LeetCode - String to Integer(atoi)

Description

string을 integer로 반환하는 atoi를 구현하라.
해당 함수는 첫번째로, 공백이 아닌 문자가 나올 때 까지 최대한 많은 공백을 제거한다. 그런 다음 첫번째 문자가 + 또는 -인 경우 부호를 택한다. 그런다음 등장하는 숫자 모두를 integer로 변환한다.

이후에도 문자가 나올 수 있으나 integer변환 이후에 등장하는 문자는 변환에 아무런 영향을 주지 않으므로 무시한다.

만약 공백 제거 이후 첫번째 문자가 숫자가 아닌 경우 또는 공백 제거 이후 문자열이 존재하지 않는 경우에는 변환이 일어나지 않는다.

이런 경우 0을 반환한다.

Note

• 공백은 모두 space charactor(' ')로 이루어져있다.
• 32비트 정수만을 저장할 수 있다고 가정한다. [-2^31, 2^31 - 1]

풀이

우선 단계를 아래와 같이 나누어보았다.
1. 먼저 string의 왼쪽 공백을 모두 제거한다.
2. string의 첫번째 문자가 + 또는 -인지 검사한다.
- 해당하는 경우 sign 변수에 부호를 저장하고 첫번째 문자를 제거한다.
3. 이후 나머지 문자열을 순회하며 숫자인 경우 answer(string) 변수에 더해주고 문자인 경우 순회를 중지한다.
4. answer를 integer로 변환하고 정수 범위에 벗어나는지 여부를 판단하여 결과를 리턴한다.

코드

Python

from collection import deque

class Solution:
  def myAtoi(self, str: str) -> int:
    # trim whitespace
    str = str.lstrip()
    if len(str) == 0:
      return 0
    # set the range of integer  
    int_max = 2 ** 31 - 1
    int_min = -(2 ** 31)
    answer = ''
    sign = 1
    # deque for storing the string
    str = deque(str)
    
    # if first letter is '+' or '-', 
    # set the 'sign' variable to corresponding value and remove that element 
    if str[0] == '+' or str[0] == '-':
      if str[0] == '-':
        sign = -1
      str.popleft()
    
    # if str is empty string or first letter is non digit character,
    # return 0
    if len(str) == 0 or not str[0].isdigit():
      return 0
    
    # iterate through the string and append every character that is digit
    for i, char in enumerate(str):
      if char.isdigit():
        answer += char
      else:
        break
    
    # convert answer to integer
    answer = int(answer)
    
    return min(int_max, answer * sign) if sign > 0 else max(int_min, answer * sign)

JavaScript

/**
 * @param {string} str
 * @return {number}
 */
var myAtoi = function(str) {
  str = str.trimStart().split('');
  if (!str.length) return 0
  
  const int_max = 2 ** 31 - 1;
  const int_min = -(2 ** 31);
  
  let answer = '';
  let sign = 1
  
  if (str[0] === '+' || str[0] === '-') {
    if (str[0] === '-') sign = -1
    str.shift();
  }
  
  if (isNaN(str[0]) || str[0] === ' ') return 0
  
  for (let char of str) {
    if (isNaN(char) || char === ' ') break;
    answer += char;
  }
  
  answer = parseInt(answer);
  
  return sign > 0 ? 
    Math.min(int_max, sign * answer) : 
    Math.max(int_min, sign * answer)        
};
    

결과

Runtime: 52 ms, faster than 19.72% of Python3 online submissions for String to Integer (atoi).
Memory Usage: 13.6 MB, less than 94.79% of Python3 online submissions for String to Integer (atoi).

Runtime: 108 ms, faster than 33.10% of JavaScript online submissions for String to Integer (atoi).
Memory Usage: 39.2 MB, less than 14.78% of JavaScript online submissions for String to Integer (atoi).

근데 같은 코드로 submit을 해도 할 때마다 차이가 좀 있더라.