[Swift 알고리즘] 백준 BOJ 10757 - 큰 수 A+B

[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로 알고리즘 다운 문제를 처음으로 풀어보았습니다.

역시 처음 배우는 언어로 알고리즘을 한다는 것을 쉽지 않다는 것을 느꼈습니다.

열심히 공부해야겠습니다.

 

감사합니다!

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.