Lv.1mathsimulationstring
아주 긴 이진수 더하기
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
0과 1로만 이루어진 두 이진수 문자열 a와 b가 주어집니다. 두 수의 합을 이진수 문자열로 반환하세요.
입력은 "0" 자체를 제외하면 0으로 시작하지 않으며, 반환하는 문자열도 마찬가지로 불필요한 앞자리 0 없이 만들어야 합니다. 두 문자열은 수십만 자리까지 길어질 수 있으므로 언어의 기본 정수형에 담을 수 없습니다.
입출력 예
| a | b | result |
|---|---|---|
"11" | "1" | "100" |
"1010" | "1011" | "10101" |
"0" | "0" | "0" |
입출력 예 설명
예 1 — 이고, 는 이진수로 100입니다.
예 2 — 이고, 은 이진수로 10101입니다.
예 3 — 입니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(a: string, b: string) → string
제한 사항
-
a.length,b.length a,b는0과1로만 이루어져 있고,"0"이 아니면0으로 시작하지 않습니다.
기대 복잡도
- 시간
- O(N + M)
- 공간
- O(N + M)
입출력 예
| a | b | 기대 출력 |
|---|---|---|
"11" | "1" | "100" |
"1010" | "1011" | "10101" |
"0" | "0" | "0" |
힌트
힌트
초등학교 세로셈처럼 맨 뒷자리부터 한 자리씩 더하고, 받아올림 carry를 다음 자리로 넘기세요. 자리의 합은 a의 자리 + b의 자리 + carry이고, 그 값을 2로 나눈 나머지가 결과 자리, 몫이 새 carry입니다.
결과는 뒷자리부터 만들어지므로 배열이나 버퍼 뒤에 차례로 붙인 다음 마지막에 한 번 뒤집으세요.
복잡도 목표
새로 구한 자리를 매번 결과 문자열의 앞에 붙이면(result = digit + result) 붙일 때마다 문자열 전체가 복사되어 이 되고 시간 초과가 납니다. 뒤에 붙이고 마지막에 뒤집으면 입니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1006 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 10 | 판정만 |
| performance | 60 | 4 | 판정만 |