Reverse the Digits
음이 아닌 정수 n이 주어집니다. 십진수 자릿수를 역순으로 써서 얻는 수를 반환하세요. 앞에 오게 되는 0은 제거되므로 120은 21이 됩니다.
함수
- ninteger
- 뒤집을 음이 아닌 정수
- 반환값integer
- n의 숫자를 역순으로 나열한 수
제약 조건
0 ≤ n < 109- 뒤집은 수도 부호 있는 32비트 정수에 들어갑니다.
예제
- 입력
- n = 1234
- 출력
- 4321
- 설명
1234의 숫자는 1, 2, 3, 4입니다. 끝에서부터 읽으면 4, 3, 2, 1이며, 이는4321입니다.
- 입력
- n = 120
- 출력
- 21
- 설명
- 거꾸로 읽으면
120의 숫자는 0, 2, 1입니다. 맨 앞의 0은 숫자에서 세지 않으므로 답은21입니다.
- 입력
- n = 0
- 출력
- 0
- 설명
0은 한 자리 숫자이며, 이를 뒤집어도 다시0이 됩니다.
제출 시 숨은 테스트 +13개
후속 질문
n이 어떤 32비트 정수든 될 수 있다면, 그 정수를 뒤집은 값이 범위를 벗어날 수도 있습니다. 곱셈으로 오버플로가 발생하기 전에 이를 어떻게 감지할 수 있을까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
어떤 산술 연산을 하면 수의 마지막 자릿수를 구할 수 있고, 어떤 연산을 하면 마지막 자릿수를 제거할 수 있나요?
n % 10은 마지막 숫자이고n / 10(정수 나눗셈)은 마지막 숫자를 제거합니다. 숫자d를 다른 숫자r의 끝에 붙이려면r * 10 + d를 계산합니다.result = 0에서 시작합니다.n이0보다 큰 동안, 마지막 숫자를result의 끝에 붙이고n에서 그 숫자를 제거합니다.0 * 10 + 0은 계속0이므로 앞에 오는 0은 나타나지 않습니다.
풀이
십진수 텍스트를 뒤집는 것은 대부분의 언어에서 한 줄이면 되며, 좋은 첫 번째 답변입니다. 면접관은 보통 문자열을 사용하지 않고 같은 결과를 구하는 방법을 이어서 질문합니다. 산술 연산을 사용하는 방법은 두 가지 연산에 기반합니다. n % 10은 마지막 숫자를 읽고, n / 10(정수 나눗셈)은 마지막 숫자를 제거합니다.
십진수 텍스트를 뒤집으세요
핵심 아이디어
숫자의 자릿수는 정확히 그 숫자를 십진수로 나타낸 텍스트의 문자들입니다. n을 텍스트로 변환하고, 문자를 뒤집은 다음, 그 텍스트를 다시 숫자로 읽습니다. 1234는 "1234"가 되고, 이어서 "4321"이 된 다음, 4321이 됩니다.
앞에 오는 0은 저절로 처리됩니다. 120을 뒤집으면 텍스트 "021"이 되고, 이를 숫자로 파싱하면 앞의 0을 무시하고 21을 반환합니다.
10^9보다 작은 숫자는 최대 9자리이며, 처리 작업과 추가 텍스트는 모두 숫자의 자릿수에 비례해 증가하므로 O(log n)입니다.
알고리즘
n을 십진수 텍스트로 변환합니다.- 문자를 뒤집습니다.
- 뒤집은 텍스트를 정수로 파싱하여 반환합니다.
def reverseDigits(n):
# int() ignores the leading zeros that trailing zeros turn into.
return int(str(n)[::-1])산술 연산으로 숫자 꺼내기와 넣기
핵심 아이디어
n의 끝에서 숫자를 하나씩 떼어 새 숫자의 끝에 더하세요. n % 10은 n의 마지막 숫자이고, 정수 나눗셈으로 n / 10을 계산하면 그 숫자가 제거됩니다. 숫자 d를 result의 끝에 더하려면, 현재 값의 자릿수를 한 자리 왼쪽으로 옮기고 일의 자리에 d를 넣으세요: result * 10 + d.
1234의 경우, n이 123, 12, 1, 0이 되는 동안 result는 4, 43, 432, 4321이 됩니다. n이 0에 도달하면 반복문이 멈추므로, 숫자 하나당 한 번 실행됩니다.
앞에 오는 0은 나타나지 않습니다. 120의 경우, 처음 떼어 내는 숫자는 0이고 0 * 10 + 0은 여전히 0이므로 흔적을 남기지 않습니다. n = 0이면 반복문은 실행되지 않고 답은 0입니다. 정수 두 개만 유지하므로 추가 공간은 O(1)입니다.
알고리즘
result = 0으로 설정합니다.n이0보다 큰 동안 마지막 숫자인n % 10을 계산합니다.result = result * 10 + digit로 설정합니다.- 정수 나눗셈을 사용하여
n = n / 10으로 숫자를 제거합니다. result를 반환합니다.
def reverseDigits(n):
result = 0
while n > 0:
result = result * 10 + n % 10 # push the last digit of n
n //= 10 # drop it from n
return result
함정과 경계 사례
대부분의 버그는 나눗셈과 반복문의 끝부분에서 발생합니다.
- 정수 나눗셈이 필요한 곳에 일반 나눗셈을 사용하는 경우입니다. JavaScript, Python 3, Lua에서는
n / 10이123.4를 반환하므로n은 다시 정수가 되지 않고result에는 소수 부분이 계속 쌓입니다.Math.floor,//또는 해당 언어의 정수 나눗셈을 사용하세요. - 반복문을
while n >= 10으로 작성하는 경우입니다. 마지막 자릿수를 처리하기 전에 반복문이 끝나므로1234는432로 반환됩니다. - 뒤집은 텍스트를 숫자로 변환하지 않고 반환하는 경우입니다.
"021"은 숫자21이 아니므로 예상한 답과 비교할 때 일치하지 않습니다. - R에서
as.character로 double을 형식화하는 경우입니다.n이 double로 저장되어 있으면100000000은1e+08로 출력되고, 뒤집은 텍스트는80+e1이 됩니다.format(n, scientific = FALSE)를 사용하세요.
자주 묻는 질문4
숫자를 문자열로 변환하지 않고 숫자의 자릿수를 어떻게 거꾸로 뒤집을 수 있을까요?
숫자가 0이 될 때까지 두 단계를 반복합니다. n % 10으로 마지막 자릿수를 가져와 result = result * 10 + digit로 결과에 추가한 다음, 정수 나눗셈을 사용해 n = n / 10으로 해당 자릿수를 제거합니다. 1234의 경우 결과는 4, 43, 432, 4321 순으로 커집니다.
숫자를 뒤집으면 끝에 있는 0은 어떻게 되나요?
이것들은 숫자에 없는 앞자리 0이 되므로 사라집니다. 120을 뒤집으면 21이 되고, 100000000을 뒤집으면 1이 됩니다. 산술 루프는 이를 저절로 제거합니다. 빈 결과에 0을 더해도 결과는 0으로 유지되기 때문입니다.
정수를 뒤집는 시간 복잡도는 얼마인가요?
루프는 10진수 자릿수마다 한 번 실행되며, 숫자 n에는 약 log10(n) + 1개의 자릿수가 있으므로 시간 복잡도는 O(log n)입니다. 산술 방식은 추가 공간을 O(1) 사용하고, 문자열 방식은 자릿수를 텍스트로 저장하므로 O(log n)의 공간을 사용합니다.
정수를 반전하면 오버플로가 발생할 수 있나요?
입력이 어떤 32비트 정수든 될 수 있다면 그렇습니다. 1000000009는 범위에 들어가지만, 이를 뒤집은 9000000001은 그렇지 않습니다. 여기서 n은 10^9보다 작으므로, 뒤집은 수는 최대 9자리이며 항상 범위에 들어갑니다. 입력값이 더 크다면 곱셈을 하기 전에 매번 result > (INT_MAX - digit) / 10인지 확인하세요.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def reverseDigits(n):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
n = 1234
기대값
4321