[baekjoon 10757번] 수학 1 - 큰 수 A+B
문제
두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 A와 B가 주어진다. (0 < A,B < 1010000)
출력
첫째 줄에 A+B를 출력한다.
| 예제 입력 1 9223372036854775807 9223372036854775808 |
예제 출력 1 18446744073709551615 |
문제풀이
이 문제를 푸는 원리는 아주 간단하다. 매우 큰 수는 int형이나 long형으로는 저장자체가 안되기 때문에 문자열로 받아서 한 자리 수씩 계산하면 된다.
그런데 우리가 아는 문자열은 진행방향이 -------------->이다.
만약 0부터 문자열의 길이까지 숫자들을 1개씩 불러오게되면 제일 큰 자릿수의 숫자부터 제일 작은 자릿수의 숫자 순으로 숫자들을 가져오게 된다.
그래서 문자열의 길이부터 0까지의 순으로 숫자들을 불러서 결괏값을 저장하고자 하니 이번엔 결괏값 저장문자열의 순서와 꼬이게 된다. 왜냐하면 문자열을 추가할땐 --------> 이런 방향인데 실제 계산값들은 <------------ 이 방향으로 자릿수가 커지기 때문이다.
따라서 우리는 이전 포스트에서 썼었던 StringBuilder와 비슷한 StringBuffer를 쓸 것이다.
StringBuffer 클래스를 쓰는 이유는 간단하다. 문자열의 조작이 굉장히 쉽기 때문이다.
StringBuffer를 이용하면 문자열.reverse()라는 메소드를 이용하여 간단하게 문자열의 순서를 뒤바꿀 수 있다.
따라서 처음에 생각했던 큰 수를 계산하는 과정은 다음과 같다.
1. 입력받은 두 숫자 문자열의 순서를 뒤바꾼다.
2. 두 숫자 문자열의 각 자릿수의 값들과 올림수를 더한다.
3. 계산 결과로 나온 값의 1의자리 숫자를 해당 자릿수에 저장하고 10의 자리 숫자를 다음 올림수에 넣는다.
4. 2~3의 과정을 두 문자열 중 길이가 작은 문자열의 길이만큼 반복한다.
5. 계산 결과 문자열의 순서를 뒤바꾼다.
이렇게 계산을 하다보니 처음에는 잘 되나 싶었는데 뭔가 하나가 부족하였다. 바로 계산이 끝난 후에도 올림수가 있으면 그 앞에 올림수를 더해주어야 하는데 그러질 못하여 마지막 자릿수의 숫자가 소실될 수도 있다는 점이다.
그래서 다음과 같은 과정을 마지막에 추가하였다.
6. 만약 올림수의 숫자가 0이라면 그냥 결과 문자열 그대로를 리턴하고 숫자가 0이 아니라면 문자열의 제일 앞에 올림수를 더해주고 문자열을 리턴해준다.
이렇게 하니 같은 자릿수를 가진 숫자들끼리의 계산은 문제없이 잘 되었다.
그러다가 자릿수가 다른 숫자를 계산해 보았는데 아니나 다를까 역시나 문제가 발생하였다.
따라서 이 숫자들을 계산하는 방법에는 여러 다양한 방법이 있을 수 있지만 나는 그 중에서 길이가 더 작은 문자열의 자릿수에 0을 채워서 계산하는 방식을 택하였다.
1. 입력받은 두 숫자 문자열의 순서를 뒤바꾼다.
2. 두 숫자 문자열의 길이가 더 작은 쪽의 문자열의 뒤에 append 메소드를 이용하여 문자열의 길이가 더 긴 쪽의 문자열의 길이와 맞춰질 때까지 0으로 채워넣는다.
3. 그 후 두 숫자 문자열의 각 자릿수의 값들과 올림수를 더한다.
4. 계산 결과로 나온 값의 1의자리 숫자를 해당 자릿수에 저장하고 10의 자리 숫자를 다음 올림수에 넣는다.
5. 3~4. 과정을 두 문자열 중 길이가 작은 문자열의 길이만큼 반복한다.
6. 계산 결과 문자열의 순서를 뒤바꾼다.
7. 만약 올림수의 숫자가 0이라면 그냥 결과 문자열 그대로를 리턴하고 숫자가 0이 아니라면 문자열의 제일 앞에 올림수를 더해주고 문자열을 리턴해준다.
이런 식으로 계산을 하면 모든 과정들이 딱딱 맞아 떨어질 것이다.
1.
|
1
2
3
4
5
6
|
StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());
StringBuffer a = new StringBuffer(stringTokenizer.nextToken());
StringBuffer b = new StringBuffer(stringTokenizer.nextToken());
a.reverse();
b.reverse();
|
cs |
2.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
int a_len = a.length();
int b_len = b.length();
int len; // 더 긴 문자열의 길이를 저장할 변수
if(a_len > b_len)
{
len = a_len;
b.append("0".repeat(a_len-b_len));
}
else
{
len = b_len;
a.append("0".repeat(b_len-a_len));
}
|
cs |
3~6.
|
1
2
3
4
5
6
7
8
9
10
|
StringBuffer result = new StringBuffer("");
int tmp = 0; // 자리 올림수를 저장할 변수
for(int i = 0; i < len; i++)
{
tmp = Integer.parseInt(String.valueOf(a.charAt(i)))+Integer.parseInt(String.valueOf(b.charAt(i)))+tmp;
result.append(tmp%10);
tmp = tmp/10;
}
result.reverse();
|
cs |
7.
|
1
2
|
if(tmp==0) {return result.toString();}
else {return String.valueOf(tmp) + result.toString();}
|
cs |
Junit 테스트
|
1
2
3
4
5
6
7
8
9
10
11
|
class PracTest {
@Test
void addinfinite() throws IOException {
assertEquals(prac.Prac.addinfinite("9223372036854775807","9223372036854775808"),"18446744073709551615");
assertEquals(prac.Prac.addinfinite("1","1"),"2");
assertEquals(prac.Prac.addinfinite("197","311"),"508");
assertEquals(prac.Prac.addinfinite("555505835","8591042"),"564096877");
}
}
|
cs |
결과는
결과엔 이상이 없다.
시간 테스트
문제에서 1자릿수부터 10000자릿수까지가 범위라고 했으므로 만 자릿수 1개와 9999 자릿수 1개의 덧셈을 진행하였다.
2332418522465847537630421472206057217295623697422502371205932153285626283763319392022484024315900838937900631742325575313670178100164075669265445633405000157192468541322319377957273237015615701041534683523503455254505236255778866253792586081798502420537956313317106977558044954589827770191032137812168563104224245318714330410676333616412900062859901130545515631480487837519556658225543904802580636795631817003378235366369938279801157640889843121779737269390512257501657516789184212843254887658794368258906830611634681030203008944618702052972911734782825372794125541219558194238547008628626188127953233610606622688733105296842241583291629726270883825990777730537951559676987186975953677199250326006959505167532880022543833872702928272244727179733748641776406071553166540665994167054293797127657168539701389026672786851398257313086241238532545455291591800707536870935309788098708887601199136962772661036336227960052045295919013390083000987328734391292468565004985338919291836160998856136928796814586696698162722233568612770912776122491467402427054177502366535535774084634218805374760357720969705050437575258103498285470074630004387456781498867196099198882296334001768867576950623456975439021262217260214948878787917702089897920554622948145744726592598178682626763678829873908506626378197862727073075550825234115034551170363305221356121910831442418039171484989021508256907045280549980182798322745746991111055334736443178370539221089461015781453789465805221845248901538967167633805605072348040798284282329854430084330323701591096116225026518655628924335470177954746159972611207867203918460555324576723861418927005908148979187954613649537596447807874127220043666425533043287602395094712388918806697582429743762871287340955993905086164196255957723891693541841925722085313329924876939406052918601361824639321810316525036430348736680120853825833373655040759911262506491230148576257548349942119816084404932454596682798585070026913546303293084236027331147811405486287525353643219795860806566218108801441787116821564901651080160645847758349535935689389963714028025201740363256081442969648859917637960933386288007166233500205631139079235727887836320579305558880685829295528975847865732485434344649304047908863204424014695608391787131278491792067249790004209020743445831797507698068403683092022817982593215029671080671412264138925973237587317816804009478946811382017994811323270215058400053695521580574210939237813051804718306902401219905576421229197508214577273511113314092481034346578722363334023982623967433705460949226736606236215993873318638480169554984171691448414591610061275959147641257657538260334873226061327633080975053774959010159335959098795061244255820267218206181970515176941728506799512753092563048874826454696527275311536257437003899201278791929085209412268738939901929433725991905756743927770012907298847992741356261805108694405570408075121484145769464405366848264840788240364455193706033012289617999135940665177303603107465140253726682934437832365079017802431770525130488845630437806047114953978842670147609204354508459413314635018519986825260182854367775950241431663747476348616442599030147468467668484156793419202754428921417647022214628525433721180163182365761897195617216516236518178241772690841705244600105045232613424573264344569575849288874658866707326406059027640567045714393329098699142183032474623352711810569165490666596496260422373355676180764205361407489134567040645949127605737664513449595816870755779191596161720150298135919137634167302367175795080937377335085149264612563181654859593745035873545966259993025870963365440831102070680485819051236209807532823863663369650375626304962545378964689083670924743650874740842329030026300529071407356074715114467572022283649509385993239236768746020042934205782352574447458558530837640512044932259906168797457024092743163489886622689020975208901634477946723708717768260150619589090898035312785731748878242933566513213161568310453894211704049495700642688028571258434247862242977836156786321246761526229283399111361065759307726977940170687629303217138333478115441511926634239045166172307592791603131048834629716613367066999853244060919800134863266504669291130251190489156626055441532219847581854267427031606481428011701956671680236868454554943931462240681175483033459737920989036847245171825689766104469044799986532984581628848875577677816888335485611809168264852391384788700881674017515514064632647608297020045805110046491913769710514985243813487351047314458421321397254879516196223082847821266613025477795104418023040043005691296999379467156408112584740959632935249574974179352191159273026182371245065409747476947424782770443704076074795326350519886943651693527645330700643798255448936132630818841800022420427302182679613532882251886387871112809537218726252663924766661966615987112317035573326054412747368872811304116158150762761942388309266802441876194661086399253806364834713651600502426325362507305528102412075172723368962048492292139708892818212161535493934399113385193257273815627291547274069421302739096685403388351390956860158639058752925107150919480979766199378100780583944135883259755942286549864404149231002397911110948845725869914288616377041863013137789872531003675036325548863906971418036495223396810252510669622439608111050773517050108673137675484146104207307997988220548425892082235026762270770234409892983745204295179833146295449977181321927983846963261163927148249798393391879919136871724957054451107478229910998468977815145940188183903980562117174918013245127855551389082754970308338475964276645050131601599414185507830201379585024861372042575773650582729231128887398101364945479707278634372073052894102719917414275964079010501631708022549749912171381124419633505801472862108802955496880328505721559370205703196113063952130602500827699863868568009465511914865426473823599435478243243480879086254396703560172559685186850531520142408314416064360640420417725651679098898237643577908814985424331540794632943007328950890930576466620403987950716467619111386018251099075828492960719479663977405189105147252082332067776766708090370614229220307559700430476316201300622074301013299379084296597958414843156816405388882566559247382251327398597560452117222802549140739927221298666831273350732183232913168383544034866915703955292064974892609913154542964289997574036405749671212103103823943697207485909640048103814814202514132007655473148818628097267671128104871736086394142203576400400654661146204235069385926492442722143814390903367766361201240647431034342665384627017395801589550608407019161648362620744643804071791812662609402292706225056066573446850295876640301435112180423465467865736428440287752479382072645305263669881137336489004417634250349754699786748837755316383265134339848821026987999501069571491831621912154364239080314005803063243123539567303005007012323602229798986265112995158442154305678765043507683211709628735491389790928992070270574568796791278099316622638901166533829750442487263542057326465798676918634376434560669174605659811154736356297220968875150470100703752406623947306431900158180532099054489154511269344715007211579122299281662096597480703522496821893613928515486691544270360269869739096217263267272742193802123946186202758580161629344420042368905916386416332050600614057796088938000559544515613659909676568645430315617683032151523031826685039950064043928745151220860566175572054975903233302850331168867238012862318161140306843484608825104455073369795372715446193155205973944184533184891040294218886139125368785923132488057049831117470994050242447762478928388682388851797562560724041011728359899280216257913822092957732419931595772028631434087597545847940312117210549363709886550253251737227068492768342570635203885944727061335696928846899325736039333833432832995220689627575611804510146632366866907112565936130184172300815909704833814412997560812859548678997232709930800447680045843263622069148908221724987756126539568702908447739987441452120944159039868246523268550025925637680975594256724842808037183719050950785179467011592343943132772523702300878733442411285374460081631744064433735434454621793458855612701698598763754831579382720126387826246033997877261274185066866382442032200673331747029865104605411948692015976235909813873217370881620998212177303568500306601606811028546287758232471625992037041676344545568358958311894335466661814198134013440723012280215909207842660771899836890958782457935712402669042878231338835975230884027994572483904397222401827264139771151888917207532254360171120362944438495925631609454030263532606925268891805641595536468857931265581456714959846208352460533164754913597728175787200067844624099905366089556188286572443992302869120444332398047821918422608818582751859857221883864577280592308765745828529734969015417023828753640800851323396850628572954330362135418430348718607556797024357582024283637091283256654686548379888938501971824683190618524093111628575044276310465083945969477959659048177984445455304898763589356005893474547726528943104847192137111738541903377404974435968678223909883856968126420612838149073166205402907730989320486604986108575402236298543746838145845246912159335542334053454602501302285308767203972014868810449797891004907093454657490976223007376561705752763839033250251859804691316516970998267811561441058056740497335789583736479889681859249225154660250536412072551460306286152011337171956161971795541972160739255721285979266531294755833376484908611437782462587541658588352149233127106992400190203822342531528911334634800865407048098479918892427326465416393311805783744150228375139372104749327714833377934767251363423659292570800472956951454667953623486184470338932351960494618862187089685479467150417722138077991244254465315179450141754102388108017218764958526706229763191763841177270978706422798939476090063507288319323419318978649547782704973400937764856582797945108575159496065513705789248422887104511200229974767784921608279974470413034329050868722512918074849570076977191447278713799588753586944668304157282274653210773646626902457578490786842517485701199393337075400102506551716381686336123073045389706943366938650748179487013012482707098844
021969881612896613915031493413349490864709798031949175480184883561598049929207764244536520261402980804261824517332622509653029205589647474831871306195424491695705838200956751981918670320559418211939570490085783195929905288037047507941004481505085698055133669976711129388825581859860848136316338809925781506447221285632334177811603982179861738695442330849104403035127281911741721558215318913724198568395899160493678309827273719575635441678290427165558319526230127978822259648871430542475364381216920131618603819787367193668049263017458100302322790618553489066400940291689262880704018983827963678295504912614362875488415801607865395146670970000107311069238906461200749847703994802275018482554732348499766163525707881845358091457017298813375206895443159389691061392896762454352699420144749931691346290339533497028276081348162471519500261096940691470541341398785081106824168017003691532223117933243141439466295776579589385450886299195592279917121439213114965163638274697335781548004421536334140422945787186402155900742566232378050166357425585330948280672156780551808950755164469359207156306962183327763205813378515455461986250711666890088303995518425673250819172801946795929269724322316823721002374844237076609825414551941864873843233724130360626090361891649624916450815365880733179334995545089884470984277524127159753493032273250879584010477361660281654455085352212187490216684383557123138867280150834413224016372482078518659115429053731597195495218503902847682684277834543272133054001931676224730855032730489487788033221555205089991232199438531180703818103187097296195946477636102189409679831436749371698198154765275540353007150710177044506029552904490139860762129378247786469009289466810079045210219342901886441903434587705499575314007271818465546008111880417775850761816173776611853285635698162856463313313190974896087096613284933973343217282554053934458637021168298722002387033812440270849186525839698248978616175307310415352747698074418130939496038333078538396284599140238873555900344399442813514719462556068878518807977859648593570782684912781788513368900667767323546137195878531961302827304167447181406748316747454228912716121851293447322986527062738128312495726273892870962250938176648243952285038881872575929392538360764294782803652468166441089101132096276641941060552086382663893339091262683383199677436092696289213318467903276251989191606588277186251786393578847094765060769587970160359173257916656473122703124116063504386445121927652089214744924796479795400819547174495290518566916024458822553594605976422679792465084071496045385858425148223341512542438860391553440213880028746696888164442931738547855980606434834756942460658071339224452781134736419085006461223784917965370364557901416316433424258660124080166458352787572114089282667070730323629065660695891853418509719958608924848761494851891510468120031751147169160795803831659979892287285435465287659961015395381650723543741294977114445044704152420349613015612070659151877354019647912530214924631180188531623576393946855139093908499891714666425788695109348341924226376439925864084070676988999596226763232697434818831796444046804582475966121545834361809330549202332241415862319236133487259542659665371548658747501395185295106767276774765145815928246691142999932986707659795307911474820756839477316523562948596222995600458685485943297367390725436452756640875895943254710019485753858571433034764860045085387509377960667052146245623123647541506506590898973542294652376679381798404267976841859539829106276593282614790799053232894670158269344220659502544862751330097751929618677675564539833085223263455590290198067195735508133604349299176500093168422741301869432712578464218888854451886218694814988844987923579280140453408457166373856969132588141305225322863624474001893464794374695021005613687924307436862892427610206937140088076841526312940229119110962695764815235424573243797609649979681501321705194214506042731368336270258179576317767794082531992595812871524146858816422599631726712462641973356509165039885617982236532793444754681754409955440746423112193067584031073864205099224433147872779173265353865419723343006118106551488921324317356007146476116460599480595115314841260220349898422588530299473536442883184135513580586610821387195304645173491134580219834326457710389832683618855066205043457091400284421701935474664345646997054297614263486864689355879561239183178548118767508408371082085739475210571779456723121141577527246604872519263064697204331127081044022242755257068837568014642957073789541873897081137633194456679830059725351656057663811691595251949614803934395398096123510652837435486167263808101845768104588418171045656270287879465250339634361268369209821843700796596693237153544432650778247934796490072114208179485746082963224817677116162388219859052446458843091914317894685811935600179134772563197200446808954052484859691200117421600543053256617972615304726823382839849511377247690253091091687227156457929432175361856924011281635367640192248462445210175581498617970072444004977144644054897821427923425322841651026182726616561698522109855182673886835651041519831824029316788446375659684839595792325561376102602823594929734645234449518253066738606886456479693194432383407250831908946498872508499427158569683190945484218449459408239689452150455045943489503746221939614398406757571041794246295975291605062198778660425809762214677107034265243310434325280061856529684758068721750163299431769910379459389764599756519786702872818395882719180241009059137132499773477034671753168114314341891333867338167644082431707301356571834654156707706067929105899485744303274712312453093080335001592777793389988170825486724191442213097080969168681867594742516154255086999236710083876762094305631665284466874485397105207825624410714873087966181214168342926644389076238821003437959046258329461869633877350809125710089008988278543275111686183252261189094068094626192041444588004901584823640924091633675464322086407653160500298021944787885638713571889043419685128269394912308658077407663874407288784312886365397419269617707753380272935148000345807108408760001359291793320236599500344351952396847568208662362908892480113770806518403137527851595497010031274083721300465858663789006152432085558331374113523385788472694750849852816873014248692597645802752285679331459337824250398047335196375132797850633508649265993338246299267308071147830439753482589013685638494851813447241740790107231329147376544394440531145517826552202425593145535112510479928473955501257494099880658750301806301353725286243357435529653216151284085802869344395425829155877579275596194111636721643151435574349335308612354995113743836447961643084216971776930269019667453546941185201329300743322653587310446569810624905784065967445297133931263716606901161097286137937826736121565961348388712792445150274245903061256554580312226544833850109092310634963592264877651335207327078767127904500502391169932220327181237189413380423703130150060951130103814798793807537961189962223810041787975363856489639877723624743347909576905531065640950872081885202090961408680298170593258375958909439557271813959024486722497724895487634435077047719228601419716773220729665293735394340464803432003498977065442756157467761179046407618050009464893527064713487789575711878618949175695060978615146487498307074685832551961648767902463520448978031982506828052505110062472585967018792413642436657516247587532104980472746866343630379355336118497905989669773469614952868188749646187996332974639399446810089123439174916470891922392723925676434362815268785795506593216894405508186569424484086488673132029366764929618328551666222531914490045515376425587918050526987705001032187095944697486131521024527652140946089353762134317049849418953386188409078491157828052096313753034745445477848732549990604263251193352861991949974410783972620399378274244349368987189846284295375543557478440064985571129131106441900517136318868828904642183950448134906093416766116257376270807173084815003998662455310704813277056086733746525090366963098747311445294402458449983825303128138030129596426035476993638345320808421812921870661570804913647310860624951157001393450959404109381863039730301192819450335663962914276346060782981614613424796411464557135112107870676874193598250919556040143432888631156991744911250522157526440564706919022387057792479180197508690313550513006422343780115911158019269536034458265613244124330608343307586033181842153492850354863849690807595961091901797226142439200575074946007168324613497645931893765932752674461305318681189001093727190329953672790295971354830693264535321599583393148362346417994287153428593509957898639440839691097139111506898048398870599587810492501493418537804747324770316266699526500789024240327810739796731220708128148288944185540743465008913753738878228783866064034495456942331121650061249530518308431331815381347955686546614051373028943023968532559706367105848295895754570521385705283718630572841239027263384826607322379825330905920401785250819579586668634496203665154729357799798421407042615970371418628772654475535658273411118932050197795041115761232526169439281508252969464633477464687342392444450249847913764083611942321543027886892914203223322834798787190592662842615506819160375507965920858969325250966135273003234085505095475144465769009896035362829739687903219159549457114852434139914810217726124619315617735930540428544347645977981287202944321747996582962943174883947720118306723379050738488673913014892480222252156535929957361747321954601736563810474579846628970440022946165007368661954689407201917417803534536202705652059506049437742886635968912197754880348394502593920718176207450449663016281287647215456442129365766664321982877681879017192671349268693902737028136327599661393709241314802057341904698386668089328542001716275318048204386417171749572739439737977490203655470120920084214083458501370811887476301649996412541564085317776535671656598178556697235629038555489359527715501591127339045823950579097935466689794925229254011466902115478244162104167119927061005723601152373232439345578152587434450074746312168775636497313454727621193598532907287816365198736907249471430497179862
결과는
1초 이내로 완료한 것을 볼 수 있다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
import java.io.*;
import java.util.StringTokenizer;
public class Main
{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static String addinfinite() throws IOException {
StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());
StringBuffer a = new StringBuffer(stringTokenizer.nextToken());
StringBuffer b = new StringBuffer(stringTokenizer.nextToken());
a.reverse();
b.reverse();
int a_len = a.length();
int b_len = b.length();
int len; // 더 긴 문자열의 길이를 저장할 변수
if(a_len > b_len)
{
len = a_len;
b.append("0".repeat(a_len-b_len));
}
else
{
len = b_len;
a.append("0".repeat(b_len-a_len));
}
StringBuffer result = new StringBuffer("");
int tmp = 0; // 자리 올림수를 저장할 변수
for(int i = 0; i < len; i++)
{
tmp = Integer.parseInt(String.valueOf(a.charAt(i)))+Integer.parseInt(String.valueOf(b.charAt(i)))+tmp;
result.append(tmp%10);
tmp = tmp/10;
}
result.reverse();
if(tmp==0) {return result.toString();}
else {return String.valueOf(tmp) + result.toString();}
}
public static void main(String[] args) throws IOException {
bw.write(addinfinite());
bw.flush();
bw.close();
}
}
|
cs |
느낀점
옛날에도 이 문제를 한 번 풀어봤었는데 그때보단 훨씬 더 아는게 많아져서 조금 더 괜찮은 결과가 나온 것 같아 뿌듯하다.