[프로그래머스] 두 수의 합

머리말

문제 링크

코딩테스트 연습 - 두 수의 합 | 프로그래머스 스쿨

이 문제를 선택한 이유

• 구현 문제 연습
• 문자열

풀이

주의점

• 문제의 조건에서 a와 b의 길이가 최대 100,000인 점을 주의해야 한다.
• 단순히 문자열을 정수로 변환하여 더하면, 오버플로우에 의해 오류가 난다.
• 따라서 사람이 직접 계산하는 방식(혹은 논리회로에서 전가산기의 방식)으로 접근해야 한다.
• 숫자를 맨끝에서 더하면서 자리올림과 나머지를 나누어, 새로운 배열에 추가할 것이다.

풀이 순서

1. 우선 파라미터의 값 중에 큰 수와 작은 수를 구분하여 각각 할당한다. (bigNumber, smallNumber)
2. 문자열을 정수를 요소로 갖는 배열로 새로 할당한다(bigNumberArr, smallNumberArr)
3. 각 자리를 더한 값의 배열(sumArrReversed, 끝에서 더하기에 순서가 반대)과 자리 올림(carry), 나머지(rest)를 초기화한다.
4. 인덱스에 대한 반복문을 큰 숫자 배열의 맨 끝에서부터 맨앞까지 반복한다.
5. 여기서 각 인덱스의 값과 자리 올림(carry, 기본값: 0)을 서로 더한다.
6. 더한 값(sum) 중에 몫과 나머지를 구분하여 자리올림과 나머지를 구분하여 재할당한다.
7. 이제 나머지를 더한 값의 배열에 하나하나 추가한다.
8. 작은 숫자가 겹치지 않을 경우에는 3번 반복문에서 인덱스 초과가 나기 때문에 작은 숫자 배열의 인덱스가 끝나면 큰 숫자와 자리 올림만 더한다.
9. 맨끝에 자리 올림이 남아 있을 수 있기 때문에 조건문을 더하여 자리올림이 남아 있을 경우 그 자리올림을 더한 값의 배열에 추가한다.
10. 현재 구한 더한 값의 배열은 순서가 반대이기에, 뒤집은 이후 요소를 String으로 바꾸어 합쳐준다.

import Foundation

func solution(_ a:String, _ b:String) -> String {

    var bigNumber: String = ""
    var smallNumber: String = ""
    
    if a.count >= b.count {
        bigNumber = a
        smallNumber = b
    } else {
        bigNumber = b
        smallNumber = a
    }
    
    let bigNumberArr = bigNumber.map { Int(String($0))! }
    let smallNumberArr = smallNumber.map { Int(String($0))! }
    
    var sumArrReversed: [Int] = []
    var carry: Int = 0
    var rest: Int = 0
    
    var j = smallNumberArr.count - 1
    for i in stride(from:bigNumberArr.count-1, through: 0, by: -1) {
        if j >= 0 {
            var sum = bigNumberArr[i] + smallNumberArr[j] + carry
            carry = sum / 10
            rest = sum % 10
            sumArrReversed.append(rest)
        } else {
            var sum = bigNumberArr[i] + carry
            carry = sum / 10
            rest = sum % 10
            sumArrReversed.append(rest)
        }
        j -= 1
    }
    if carry != 0 { sumArrReversed.append(carry) }
    
    return Array(sumArrReversed.reversed()).map { String($0) }.joined()
}

 

꼬리말

이중 인덱스 접근에 대한 어색함

• 분명 두 수를 더하는 방식은 이해가 갔지만, 부등호(>=)에서 등호(=)를 빼먹는 등의 사소한 실수로 계속 인덱스 초과가 떠서 아쉬웠다.

시간 초과(?)

• 처음에는 더한 값의 배열(sumArrReversed)이 아닌 큰 숫자 배열(bigNumberArr)과 작은 숫자 배열(smallNumberArr)을 먼저 뒤집었는데 시간 초과가 떴다…
• 문제의 원인이 무엇인지 다시 살펴봐야겠다.

// 시간 초과 풀이
import Foundation

func solution(_ a:String, _ b:String) -> String {

    var bigNumber: String = ""
    var smallNumber: String = ""
    
    if a.count >= b.count {
        bigNumber = a
        smallNumber = b
    } else {
        bigNumber = b
        smallNumber = a
    }
    
    let bigNumberReversed = Array(bigNumber.map { Int(String($0))! }.reversed())
    let smallNumberReversed = Array(smallNumber.map { Int(String($0))! }.reversed())
    
    var sumArrReversed: [Int] = []
    var carry: Int = 0
    var rest: Int = 0
    
    for i in 0..<bigNumber.count {
        if i < smallNumber.count {
            var sum = bigNumberReversed[i] + smallNumberReversed[i] + carry
            carry = sum / 10
            rest = sum % 10
            sumArrReversed.append(rest)
        } else {
            var sum = bigNumberReversed[i] + carry
            carry = sum / 10
            rest = sum % 10
            sumArrReversed.append(rest)
        }
    }
    if carry != 0 { sumArrReversed.append(carry) }

    return Array(sumArrReversed.map { String($0) }.reversed()).joined()
}