Binary to Decimal
음이 아닌 수를 2진수로 나타낸 문자열 s가 주어집니다. 이 수의 값을 일반 정수로 반환하세요. 문자열에는 앞에 오는 0이 없으며, 0인 경우에만 예외적으로 문자 0 하나로 나타냅니다.
함수
- sstring
- 숫자의 이진수 자릿수
- 반환값integer
- s의 값을 정수로
제약 조건
1 ≤ s.length ≤ 31s에는0과1만 들어 있습니다.s는1에서 시작합니다. 단,s가"0"인 경우는 제외합니다.- 내장된 진법 변환 기능을 호출하는 대신 숫자를 직접 읽으세요.
예제
- 입력
- s = "1101"
- 출력
- 13
- 설명
- 오른쪽부터 읽으면 각 자리의 값은 1, 2, 4, 8입니다.
1101에는 8, 4, 1의 자리에 1이 있으므로8 + 4 + 1 = 13입니다.
- 입력
- s = "0"
- 출력
- 0
- 설명
- 단일
0에는 어떤 자리에도 1이 없으므로 그 값은0입니다.
- 입력
- s = "10000000"
- 출력
- 128
- 설명
- 유일한 1의 오른쪽에는 0이 일곱 개 있으므로,
2^7 = 128의 자릿값을 차지합니다.
제출 시 숨은 테스트 +16개
후속 질문
2진수부터 16진수까지 어느 진법으로 쓰인 숫자든 같은 루프를 사용해 읽을 수 있나요? 이때 a부터 f까지의 문자는 10부터 15까지의 숫자를 나타냅니다.
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
십진수에서
347의 각 숫자는 각각 300, 40, 7의 값을 나타냅니다. 각 이진수 숫자는 어떤 값을 나타낼까요?가장 오른쪽의 이진 숫자는 1의 값을 가지며, 왼쪽으로 한 자리씩 이동할 때마다 자릿값은 두 배가 됩니다. 즉, 1, 2, 4, 8과 같이 이어집니다. 이 숫자는 1이 있는 자릿값을 모두 더한 값입니다.
거듭제곱을 계산하지 않아도 됩니다. 왼쪽부터 읽으면서 각 숫자에 대해 누적값을 두 배로 만든 다음 그 숫자를 더하세요. 마지막 숫자까지 처리한 후의 누적값이 답입니다.
풀이
각 이진 숫자는 오른쪽 끝에서 얼마나 떨어져 있는지에 따라 정해지는 2의 거듭제곱을 나타냅니다. 오른쪽부터 해당 거듭제곱들을 더하거나, 왼쪽부터 문자열을 읽으면서 각 단계마다 값을 두 배로 만들 수 있습니다. 이 두 배 루프는 거듭제곱을 계산하지 않으며, 10 대신 2를 사용해 십진수 텍스트를 읽을 때 사용하는 루프와 같습니다.
오른쪽부터 자릿값을 더하세요
핵심 아이디어
가장 오른쪽 숫자의 자릿값은 1이고, 그다음은 2, 그다음은 4, 8이며, 왼쪽으로 한 자리씩 이동할 때마다 두 배가 됩니다. 숫자는 1인 자릿값들을 모두 더한 값입니다. 따라서 마지막 문자부터 첫 문자까지 순회하면서 현재 자릿값을 power에 저장하고, 숫자가 1일 때마다 더하세요.
1101에서는 1(1 더하기), 0(2 건너뛰기), 1(4 더하기), 1(8 더하기)을 만나며, 합계는 13입니다. 각 숫자를 한 번씩 방문하므로 루프는 O(n) 시간이 걸리고 메모리는 숫자 두 개만 사용합니다.
power의 크기에 주의하세요. 31자리 문자열에서는 마지막 숫자에서 2^30에 도달한 뒤 한 번 더 두 배가 되어 2^31이 되는데, 이는 부호 있는 32비트 정수에 들어가지 않습니다. power를 64비트 변수에 저장하거나 마지막 숫자 이후에는 두 배로 늘리지 마세요.
알고리즘
total = 0으로 설정하고power = 1로 설정합니다.- 문자열의 마지막 문자부터 첫 문자까지 순서대로 이동합니다.
- 문자가
1이면power를total에 더합니다. - 한 칸 왼쪽으로 이동하기 전에
power를 두 배로 만듭니다. total을 반환합니다.
def toDecimal(s):
total = 0
power = 1 # the place value of the rightmost digit
for i in range(len(s) - 1, -1, -1):
if s[i] == "1":
total += power
power *= 2
return total왼쪽부터 두 배로 만들고 더하기
핵심 아이디어
문자열을 왼쪽부터 읽으면서 지금까지 읽은 숫자들로 표현되는 수인 value를 유지합니다. 이진수 숫자를 하나 더 붙이면 앞에 있던 각 숫자가 한 자리 왼쪽으로 이동해 값이 두 배가 되고, 새 숫자가 더해집니다. 따라서 각 단계는 value = value * 2 + digit입니다.
1101의 경우 value는 1이 되고, 다음에는 1 * 2 + 1 = 3, 그다음에는 3 * 2 + 0 = 6, 마지막으로 6 * 2 + 1 = 13이 됩니다. 문자열의 각 접두 부분은 더 작은 이진수이며, 반복문은 정확히 그 값을 유지하므로 마지막 숫자를 읽은 뒤에는 전체 값이 들어 있습니다.
값은 최종 답보다 커지지 않으므로, 31자리 문자열의 경우 2^31-1을 넘지 않아 32비트 정수로 충분합니다. 숫자는 문자 코드에서 '0'의 코드를 빼서 구하며, 이렇게 하면 '1'은 1로, '0'은 0으로 바뀝니다. 이것은 임의의 진법에서 텍스트로부터 숫자를 파싱하는 표준적인 방법입니다.
알고리즘
value = 0으로 설정합니다.- 왼쪽에서 오른쪽으로 각 문자의
'0'코드를 빼서 숫자로 변환합니다. value = value * 2 + digit로 설정합니다.value를 반환합니다.
def toDecimal(s):
value = 0
for ch in s:
# Shift the digits read so far one place left, then add the new one.
value = value * 2 + (ord(ch) - ord("0"))
return value
함정과 경계 사례
대부분의 오답은 순회 방향이나 숫자의 자료형에서 비롯됩니다.
- 가장 왼쪽 숫자에 자릿값 1을 부여하는 경우입니다. 자릿값은 오른쪽 끝에서 시작하므로 마지막 문자부터 순회하거나 왼쪽부터 두 배로 늘리는 루프를 사용하세요.
- 숫자가 아닌 문자를 더하는 경우입니다. 많은 언어에서
'1'은 숫자 49이므로value * 2 + '1'은 너무 큰 값이 됩니다. 먼저'0'을 빼세요. - 자릿값이 오버플로되는 경우입니다. 31번째 숫자 뒤에
power를 두 배로 늘리면2^31이 되어 32비트 정수에서 값이 순환되거나 오류가 발생합니다. - 부동소수점 거듭제곱 함수로 각 자릿값을 계산하는 경우입니다. C, C++, Java에서
pow(2, k)는double을 반환하며, 결과를 다시 정수로 변환해야 합니다.
자주 묻는 질문4
2진수를 10진수로 어떻게 변환하나요?
각 숫자에 자리값을 부여하세요. 가장 오른쪽은 1이고, 왼쪽으로 갈수록 2, 4, 8 등으로 이어집니다. 1인 숫자들의 자리값을 더하세요. 1101의 경우 8 + 4 + 1 = 13입니다.
값을 두 배로 늘리면 왜 작동하나요?
이진수의 끝에 숫자를 하나 더 쓰면 앞에 있는 모든 숫자가 한 자리씩 왼쪽으로 이동하고, 각 자리의 값은 바로 오른쪽 자리 값의 두 배가 됩니다. 따라서 기존 값은 두 배가 되고, 새 숫자는 0 또는 1을 더합니다. 첫 번째 숫자부터 마지막 숫자까지 이 과정을 반복하면 전체 수가 만들어집니다.
2진수를 10진수로 변환하는 시간 복잡도는 무엇인가요?
두 루프는 모두 n개의 각 문자를 한 번씩 방문하므로 O(n) 시간이 걸립니다. 하나 또는 두 개의 숫자만 유지하므로 추가 공간은 O(1)입니다. 31자 문자열의 경우 31단계입니다.
비트 시프트를 사용해 2진수를 10진수로 변환할 수 있나요?
네. value << 1은 값을 두 배로 만들고 | digit은 최하위 비트를 설정하므로, value = (value << 1) | digit은 value * 2 + digit과 같은 역할을 합니다. 시프트 형식은 비트를 이동한다는 점을 명확히 보여 주며, 산술 형식은 2가 아닌 진법에서도 사용할 수 있습니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def toDecimal(s):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
s = "1101"
기대값
13