문제 요약
자세한 내용은 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) - 몇개 안되는 변수를 생성하였다.