[백준 알고리즘] #10757번 : 수학, arithmetic overflow, 시간초과

1. arithmetic overflow

let readline = readLine()!.split(separator: " ").map{ Int($0)! }
print(readline[0] + readline[1])

Int 형 덧셈에서

arithmetic overflow 오류가 났는데, input으로 준 값인 9223372036854775807는 2진수로 변환했을 때 111111111111111111111111111111111111111111111111111111111111111이고 64비트의 최대값이 된다.

print(Int.max) // 9223372036854775807
print(String(Int.max, radix: 2)) // 111111111111111111111111111111111111111111111111111111111111111 -> 64비트의 최대값

양의 정수 타입인 Int는 Int32와 같이 지정해주지 않으면 컴퓨터의 플랫폼에 따라 자동으로 지정된다.

ex) 32비트 플랫폼에서는 32비트, 64비트 플랫폼은 64비트..

사용한 컴퓨터는 64비트라서 자동으로 64비트가 할당되었고 최대값의 덧셈 연산으로 오버플로우가 발생한 것이다.

 

var readline = readLine()!.split(separator: " ").map { String($0) }
var firstNumArr: [Int] = []
var secondNumArr: [Int] = []
var sumArr: [Int] = []

func makeSumArr(largerArr: [Int], smallerArr: [Int]) {
    var firstNumLastNum: Int = 0
    for i in 0..<smallerArr.count {
        sumArr.append(largerArr[i]+smallerArr[i])
        firstNumLastNum = i
    }
    for i in firstNumLastNum+1..<largerArr.count {
        sumArr.append(largerArr[i])
    }
}
for j in 0..<readline.count {
    for i in 0..<readline[j].count {
        let separatedNum =  readline[j][readline[j].index(readline[j].startIndex, offsetBy: i)]
        if j == 0 {
            firstNumArr.insert(Int(String(separatedNum))!, at: 0)
        }
        else {
            secondNumArr.insert(Int(String(separatedNum))!, at: 0)
        }
    }
}

if firstNumArr.count > secondNumArr.count {
   makeSumArr(largerArr: firstNumArr, smallerArr: secondNumArr)
}
else if firstNumArr.count < secondNumArr.count {
    makeSumArr(largerArr: secondNumArr, smallerArr: firstNumArr)
}
else {
    for i in 0..<firstNumArr.count {
        sumArr.append(firstNumArr[i]+secondNumArr[i])
    }
}

for i in 0..<sumArr.count {
    if sumArr[i] >= 10 {
        if i == sumArr.count-1 {
            sumArr.append(1)
            sumArr[i] -= 10
        }
        else {
            sumArr[i] -= 10
            sumArr[i+1] += 1
        }
    }
}

sumArr = sumArr.reversed()
print(sumArr.map { String($0) }.joined() )

2. 시간 초과

하지만 firstNumArr.insert(Int(String(separatedNum))!, at: 0) 처럼 insert해주는 과정에서 시간초과가 났다. 문자열을 하나씩 잘라서 배열로 만들어주려고 했던 것인데, 타입캐스팅하는 부분과 insert하는 부분에서 시간이 많이 걸린 것 같다.

var readline = readLine()!.split(separator: " ").map { String($0) }
var firstNumArr = Array(readline[0].reversed()).map{Int(String($0))!}
var secondNumArr = Array(readline[1].reversed()).map{Int(String($0))!}
var sumArr: [Int] = []

func makeSumArr(largerArr: [Int], smallerArr: [Int]) {
    var firstNumLastNum: Int = 0
    for i in 0..<smallerArr.count {
        sumArr.append(largerArr[i]+smallerArr[i])
        firstNumLastNum = i
    }
    for i in firstNumLastNum+1..<largerArr.count {
        sumArr.append(largerArr[i])
    }
}

if firstNumArr.count > secondNumArr.count {
   makeSumArr(largerArr: firstNumArr, smallerArr: secondNumArr)
}
else if firstNumArr.count < secondNumArr.count {
    makeSumArr(largerArr: secondNumArr, smallerArr: firstNumArr)
}
else {
    for i in 0..<firstNumArr.count {
        sumArr.append(firstNumArr[i]+secondNumArr[i])
    }
}

for i in 0..<sumArr.count {
    if sumArr[i] >= 10 {
        if i == sumArr.count-1 {
            sumArr.append(1)
            sumArr[i] -= 10
        }
        else {
            sumArr[i] -= 10
            sumArr[i+1] += 1
        }
    }
}

sumArr = sumArr.reversed()

print(sumArr.map { String($0) }.joined() )

이와 같이 문자열을 배열로 감싸주면 문자열 한 자리씩 배열에 넣어주지 않아도 한번에 배열을 만들 수 있다.