Leetcode 9. Palindrome Number - Dart, Python

Leetcode 9 문제 보기

 

1. 문제 이해하기

정수 x가 주어진다.

이때 x가 palindrome이라면 true를, 아니라면 false를 출력하라.

 

2. 아이디어 구상

우선 int x가 입력값으로 주어지므로, 이를 string으로 치환, 거꾸로 뒤집어서 palindrome 여부를 판단하면 될 것이라는 생각이든다.

따라서 Python으로 풀 경우 boilerplate code를 제외하고 한 줄의 코드면 끝난다.

<간단한 Python 풀이>

class Solution:
    def isPalindrome(self, x: int) -> bool:
        return str(x) == str(x)[::-1]

 

Dart의 경우에도 간단히 풀 수 있다.

다만 Dart는 string을 뒤집는 built-in function이나 [::-1] 같은 기법이 존재하지 않는다.

때문에

1. int를 string으로 변환하고

2. string을 list로 변환하고

3. list를 reverse시킨 다음

4. reversed-list를 string으로 다시 변환 후

string끼리 비교해 정답을 구해야한다.

 

풀이는 다음과 같다.

<String을 활용한 Dart 풀이>

class Solution {
  bool isPalindrome(int x) {
    var n = x.toString();
    return n == n.split('').reversed.join();
  }
}

 

적어도 본 문제는 이렇게 풀어도 큰 문제가 없다.

하지만 조금만 더 시간을 투자해 효율적인 solution을 고민해보자.

 

일반적으로 형변환을 진행하면 새로운 Object를 생성하기 때문에 수차례의 형변환은 시간과 메모리를 많이 잡아먹는다. 즉, overhead가 크다. 때문에 int가 주어진 경우 단순한 arithmetic operation을 활용해 연산을 진행하는 것이 더 빠르다.

 

3. 풀이

<산술 연산을 활용한 Dart 풀이>

우선 x가 음수일 경우에는 언제나 palindrome이 될 수 없다.

때문에 가지치기를 통해 경우의  수에서 제외해주자.

if (x < 0) {
    return false;
}

 

다음으로 return 시 비교를 위한 원래의 값과 뒤집힌 값을 정의하자.

var original = x;
var reversed = 0;

 

while문을 돌면서 산술 연산을 한다.

연산은 간단하다.

x를 10으로 나눈 나머지(%연산), 즉, 1의 자리 숫자를 reversed의 맨 앞 숫자로 지정한다. (eg. x=123, reversed=3)

그리고 x를 10으로 나눈 몫(~/연산)만을 남김으로 방금 사용한 1의 자리를 삭제해준다. (eg. x = 123 -> 12)

while (x > 0) {
    int digit = x % 10;
    reversed = reversed * 10 + digit;
    x = x ~/ 10;
}

By Mesotes

 

전체 코드는 다음과 같다.

class Solution {
  bool isPalindrome(int x) {
    // if x < 0, cannot be palindrome (eg. -121 != 121-)
    if (x < 0) {
        return false;
    }

    var original = x;
    var reversed = 0;

    while (x > 0) {
        int digit = x % 10;
        reversed = reversed * 10 + digit;
        x = x ~/ 10;
    }

    return original == reversed;
  }
}

 

그러나 본 풀이가 생각보다 빨라지거나 메모리 효율적이지 않음을 확인할 수 있다.

그 이유는 무엇일까?

 

Dart는 Python과 마찬가지로, 모든 것이 객체다.

즉 단순한 int 조차도 Object의 하위 클래스다.

따라서 x = x ~/ 10와 같은 연산을 하게 되면, 메모리 상에 새로운 값(x ~/ 10) 생성되고 x는 이를 참조하게 된다.

때문에 산술 연산을 진행해도 마치 형변환을 하는 것처럼 overhead가 발생한다.

 

만약 primitive types를 지원하는 C나 C++, 혹은 Java 코드였다면, 산술 연산을 이용한 코드가 형변환을 진행한 코드보다 더 시간과 메모리적으로 효율적인 결과가 나왔을 것이다.

 

---

Leetcode 9. Palindrome Number

https://leetcode.com/problems/palindrome-number/​

​

 

 

 

-문제해결흐름을 간단히 정리한 주관적 포스팅-

 

-부족한 설명이 있다면 부디 조언 부탁드립니다-

 

 

 

 

이 포스팅은 쿠팡 파트너스 활동의 일환으로,

이에 따른 일정액의 수수료를 제공받습니다