[Swift 알고리즘] BOJ 10757 - 큰 수 A+B
안녕하세요. 개발 중인 정주입니다.
오늘은 BOJ 10757번의 큰 수 A+B를 풀어보았습니다.
Swift로 Big Integer 문제를 푼 건 처음이었습니다.
다른 언어로는 풀어본 적이 있어서 푸는 방법은 아는데 그것을 Swift로 구현하는 것이 포인트였습니다.
Github
https://github.com/jeongju9216/swiftAlgorithm
문제 정보
번호, 이름 : 10757 큰 수 A+B
분류 : 수학, 구현, 사칙 연산, 임의 정밀도 / 큰 수 연산
문제 링크
https://www.acmicpc.net/problem/10757
풀이
큰 수 문제는 Int형의 최댓값을 넘는 input이 들어왔을 때 처리를 어떻게 할 것인가가 문제 포인트입니다.
파이썬은 큰 수를 자동으로 처리해주기 때문에 고민하지 않아도 되지만
이외의 언어로 문제를 푼다면 처음 한 번은 고민을 해봐야 하는 문제일 겁니다.
문제 풀이 방법은 input을 String으로 바꿔서 자리마다 따로 계산하는 것입니다.
이후 하나의 String으로 출력을 하는 것이죠.
1차 코드
let input = readLine()!.split { $0 == " " }
var inputA = Array(input[0]).map { Int(String($0))! }
var inputB = Array(input[1]).map { Int(String($0))! }
if inputA.count > inputB.count {
let diff = inputA.count - inputB.count
for _ in 0 ..< diff {
inputB.insert(0, at: inputB.startIndex)
}
} else {
let diff = inputB.count - inputA.count
for _ in 0 ..< diff {
inputA.insert(0, at: inputA.startIndex)
}
}
for i in 0 ..< inputA.count {
inputA[i] += inputB[i]
}
for i in (1 ..< inputA.count).reversed() {
if inputA[i] >= 10 {
inputA[i-1] += 1
}
inputA[i] = inputA[i] % 10
}
var stringA = inputA.map { String($0) }
let result = stringA.joined(separator: "")
print(result)메모리 : 62764 KB
속도 : 16 ms
코드 길이 : 734 B
처음으로 제출한 코드입니다.
Swift로 Int, String을 넘나들며 처리하는 작업이 처음이라 최대한 알기 쉽게 작성하였습니다.
1. 첫 번째 입력과 두 번째 입력을 Int가 아닌 String으로 받고 한 글자 한 글자 배열로 만듭니다.
2. 자리수 계산을 쉽게 하기 위해 두 배열의 길이를 같게 합니다. 이때 계산에 영향에는 주지 않기 위해 0으로 채워줍니다.
3. 각 자리수를 더해줍니다.
4. 두 수의 합이 10이 넘으면 다음 자릿수로 올림 합니다.
5. 배열을 String으로 출력합니다.
2차 코드
func convertStr2IntArr(_ string: String) -> [Int] {
return string.map { Int(String($0))! }
}
func insertZero(_ arr: [Int]) -> [Int] {
var arr = arr
let diff = abs(diff)
for _ in 0 ..< diff {
arr.insert(0, at: arr.startIndex)
}
return arr
}
let input = readLine()!.split { $0 == " " }
var first = convertStr2IntArr(String(input[0]))
var second = convertStr2IntArr(String(input[1]))
let diff = first.count - second.count
if diff < 0 {
first = insertZero(first)
} else {
second = insertZero(second)
}
for i in (0 ..< first.count).reversed() {
first[i] += second[i]
if i > 0 && first[i] >= 10 {
first[i-1] += 1
first[i] = first[i] % 10
}
}
let result = (first.map { String($0) }).joined(separator: "")
print(result)메모리 : 62764 KB
속도 : 16 ms
코드 길이 : 789 B
함수로 만들면 메모리, 속도, 코드 길이 중 하나라도 개선되지 않을까? 생각이 들었습니다.
함수 공부 겸 중복되는 반복문을 함수로 바꿨습니다.
결론은 코드 길이만 길어졌네요. 가독성을 위해 함수명을 길게 지었기 때문인 것 같습니다.
전체적으로 중복 코드가 줄어들었고 가독성이 늘어나 뿌듯했지만 가독성을 포기하고 코드 길이를 챙겨보기로 했습니다.
최종 코드
func ct(_ string: String) -> [Int] {
return string.map { Int(String($0))! }
}
func iz(_ arr: [Int]) -> [Int] {
var arr = arr
let diff = abs(diff)
for _ in 0 ..< diff {
arr.insert(0, at: arr.startIndex)
}
return arr
}
let i = readLine()!.split { $0 == " " }
var f = ct(String(i[0]))
var s = ct(String(i[1]))
let diff = f.count - s.count
if diff < 0 {
f = iz(f)
} else {
s = iz(s)
}
for i in (0 ..< f.count).reversed() {
f[i] += s[i]
if i > 0 && f[i] >= 10 {
f[i-1] += 1
f[i] = f[i] % 10
}
}
let result = (f.map { String($0) }).joined(separator: "")
print(result)메모리 : 62764 KB
속도 : 16 ms
코드 길이 : 639 B
변수, 함수명을 최대한 축약하였습니다.
최종이라고 적어놨지만 사실상 최종은 2차 코드이고 이건 알고리즘을 위한 알고리즘 코드인 것 같네요.
아무튼 코드 길이는 줄어들었으니 시도는 성공입니다.
마무리 인사
오늘은 Swift로 알고리즘 다운 문제를 처음으로 풀어보았습니다.
역시 처음 배우는 언어로 알고리즘을 한다는 것을 쉽지 않다는 것을 느꼈습니다.
열심히 공부해야겠습니다.
감사합니다!
아직은 초보 개발자입니다.
더 효율적인 코드 훈수 환영합니다!
공감과 댓글 부탁드립니다.