[Leetcode] #7 Reverse Integer 수를 반대로 뒤집어라!

문제 요약

자세한 내용은 leetcode에서 확인

https://leetcode.com/problems/reverse-integer/


수(integer)를 반대로 뒤집어라. 만약 수를 뒤집었을 때 오버플로우가 난다면 0을 반환해라.


예제

input: 123

output: 321



풀이

여러 가지를 시도해본 결과 최적화된 답은 다음의 공식을 사용하는 것이다. 

currentSum = (currentSum x 10) + digit


123을 예로 들어보자.

(0 x 10) + 3 = 3

(3 x 10) + 2 = 32

(32 x 10) + 1 = 321


수(integer)에서 숫자(digit)를 찾아내는 방법은 modulo이다. 

123의 1의 자리는 123 % 10 = 3이다. 그다음 123을 10으로 나누어서 수를 12로 만든다.

12의 1의 자리는 12 % 10 = 2이다. 그다음 12를 10으로 나누어서 수를 1로 만든다.

1의 1의 자리는 1 % 10 = 1이다. 그다음 1을 10으로 나누어서 수를 0으로 만든다.

수가 0이 되면 멈춘다.


이 두 가지 공식을 합쳐서 문제를 풀 수 있다.


public int reverse(int x) {
int sign = 1;
// 만약 negative의 수라면 마지막에 -를 붙혀 반환하기 위해 저장해놓는다.
if (x < 0) {
sign = -1;
}
// input 수를 절대값으로 변환한다.
x = Math.abs(x);
int curr = 0;
int prev = 0;
while (x > 0) {
int digit = x % 10;
curr = (curr * 10) + digit;

// 결과 값을 다시 거꾸로 계산한다.
int newPrev = (curr - digit) / 10;
// 만약 prev와 newPrev의 값이 다르다면 오버플로우가 생겼다는 뜻이다.
if (prev != newPrev) {
return 0;
}
x /= 10;
prev = curr;
}
return curr * sign;
}


Complexity

time: O(log(n)) - n이라는 수에 log(n) 만큼의 숫자가 있다.

space: O(1) - 몇개 안되는 변수를 생성하였다.