U E D R , A S I H C RSS

Primary Arithmetic/1002

처음 접근

문제 자체 읽으면서 그냥 뻔해보이긴 했다. 이전에 디지털 공학 수업때 가산기에 대해서 배운바도 있었던 관계로. 그냥 머릿속에 대략의 할 일들이 그려졌다.

그래서 첫 테스트를 바로 작성하였다.

~cpp 
class PrimaryArithmeticTest(unittest.TestCase):
    def testCarry(self):
        self.assertEquals(0,carryCount(123,456))

하지만, 그렇다고 바로 알고리즘을 구현할 수 있는건 아니여서, 일단 다음과 같이만 작성하였다.
~cpp 
def carryCount(one,two):
    result = 0
    return result

class PrimaryArithmeticTest(unittest.TestCase):
    def testCarry(self):
        self.assertEquals(0,carryCount(123,456))

그리고 할 일을 좀 생각해보았다.

1차 알고리즘 생각

문제를 이리저리 나눠보니, 자리수 하나에 대해서 carry 가 발생하는지를 세는 것이 쉬워보였다. 그리고 해당 스트링을 일종의 list 로 나누는 것도 있으면 좋을 것 같았다. 그리고 carry 에 대해서 추후 앞자리에 더해주는 작업 등을 해야 할 것 같았다. 일단은 이정도 떠올리기로 하고, 앞의 두 일만 하였다.

~cpp 
def hasCarry(one,two):
    return one+two >= 10

.
.

    def testCarryOne(self):
        self.assert_(not hasCarry(3,5))
        self.assert_(hasCarry(5,5))
        self.assert_(hasCarry(8,5))
~cpp 
def toList(number):
.
.
.

    def testToList(self):
        self.assertEquals([1,2,3], toList(123))
음.. 이 부분을 작성하던 중, 생각해보니 입력 데이터가 스트링이면 더 간단할 것 같았다. integer 단위로 더하기 보다는 자리수 단위로 생각할 것이란 생각이 들었다. 그래서 테스트 코드를 다시 바꾸었다. 그러고 보니, 그냥 구현할 방법이 떠오른다.
~cpp 
def toList(numberStr):
    return [int(each) for each in numberStr]
.
.
.

    def testToList(self):
        self.assertEquals([1,2,3], toList('123'))

2차

이 상태에서 '음.. 이정도 구현이면 어디까지 기능이 커버될까?' 라는 의문이 생겼다. 일단 만든 코드들을 연결해보았다.
~cpp 
def carryCount(one,two):
    resultCount = 0
    oneList,twoList = toList(one),toList(two)
    for eachOne,eachTwo in zip(oneList,twoList):
        if hasCarry(eachOne,eachTwo):
            resultCount += 1
    return resultCount

class PrimaryArithmeticTest(unittest.TestCase):
    def testCarry(self):
        self.assertEquals(0,carryCount('123','456'))
        self.assertEquals(3,carryCount('123','456'))
        self.assertEquals(1,carryCount('123','456'))

일단 예제로 있던 테스트 3개에 대해서는 별 일 없이 돌아갔다. 이쯤에서 걍 끝낼까 하다가, 너무 허술해보이는 것들이 많아 보였다. 그래서 해당 상황과, 그 상황에 대한 테스트의 예를 추가해나갔다.
  • 자릿수가 넘어가는 경우 - 1234 + 123
  • 103 + 597 (즉, 0+9 가 1+9 가 되면서 carry 를 다시 발생시킬 때)

carry 에 대해서는 별 생각을 안했다. 현재의 구조로는 carry 처리가 그리 이쁘게 나올 것 같지가 않았다. 코드를 좀 더 작성할까 하다가 일단은 green bar 에서 내부 자료 구조만 바꾸기로 했다.
일단, testToList 부터. 문제 스펙에서 '10자리 미만 수'라는 점을 그냥 이용해도 될 것 같다는 생각이 들었다.
~cpp 
def withNullList(numberStr):
    result = [0 for each in range(10-len(numberStr))]
    numbers = [int(each) for each in numberStr]
    return result + numbers


    def testToList(self):
        self.assertEquals([0,0,0,0,0,0,0,1,2,3], withNullList('123'))
        self.assertEquals([0,0,0,0,0,0,0,5,5,5], withNullList('555'))

여전히 테스트는 통과. 대략 추후 구현은 뻔해졌다. 자릿수 단위 계산 코드로 수정하였다.
~cpp 
def carryCount(one,two):
    resultCount = 0
    oneList,twoList = withNullList(one),withNullList(two)
    for idx in range(9,-1,-1):
        if hasCarry(oneList[idx],twoList[idx]):
            resultCount += 1
            oneList[idx-1] += 1
    return resultCount

이쯤 되니, 테스트 코드들은 전부 통과. main 코드 작성하고 약간 리팩토링.
혹시나 해서 마지막 테스트 추가함.
~cpp 
    def testCarry(self):
        testSet = [
                ['123','456',0],
                ['555','555',3],
                ['123','594',1],
                ['103','597',2],
                ['1234','123',0],
                ['1234','236',1],
                ['999999999','1',9]
                ]
        for eachTest in testSet:
            one,two,expected= eachTest
            self.assertEquals(expected,carryCount(one,two))
마지막 경우도 역시 통과. 아까보다는 좀 더 나아보여서 이즈음에서 그만 둠.

대략 끝나고 나니, 다르게 해결할 방법도 떠오름. 다른 방식으로 해결해도 재밌을 것 같다.

최종

~cpp 
import unittest

LIMIT_NUMBER = 10

def carryCount(one,two):
    resultCount = 0
    oneList,twoList = withNullList(one),withNullList(two)
    for idx in range(LIMIT_NUMBER-1,-1,-1):
        if hasCarry(oneList[idx],twoList[idx]):
            resultCount += 1
            oneList[idx-1] += 1
    return resultCount

def hasCarry(one,two):
    return one+two >= 10

def nullList(nullCount):
    return [0 for each in range(LIMIT_NUMBER-nullCount)]

def numberList(numberStr):
    return [int(each) for each in numberStr]

def withNullList(numberStr):
    return nullList(len(numberStr)) + numberList(numberStr)

class PrimaryArithmeticTest(unittest.TestCase):
    def testCarry(self):
        testSet = [
                ['123','456',0],
                ['555','555',3],
                ['123','594',1],
                ['103','597',2],
                ['1234','123',0],
                ['1234','236',1],
                ['999999999','1',9]
                ]
        for eachTest in testSet:
            one,two,expected= eachTest
            self.assertEquals(expected,carryCount(one,two))

    def testCarryOne(self):
        self.assert_(not hasCarry(3,5))
        self.assert_(hasCarry(5,5))
        self.assert_(hasCarry(8,5))

    def testToList(self):
        self.assertEquals([0,0,0,0,0,0,0,1,2,3], withNullList('123'))
        self.assertEquals([0,0,0,0,0,0,0,5,5,5], withNullList('555'))

def main():
    f=open("input.txt")
    for eachLine in f:
        one,two = eachLine.split()
        if one == '0' and two == '0':
            break

        count = carryCount(one,two)
        if count == 0: count = "No"
        if count > 1: operationMessage = "operations"
        else: operationMessage = "operation"

        print "%s carry %s." % (count, operationMessage)
    f.close()


if __name__=="__main__":
    unittest.main(argv=('','-v'))
    #main()

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2009-05-27 07:09:19
Processing time 0.0930 sec