[LeetCode 415] Add Strings (문제 설명, 해결 과정, 코드 전문, 느낀 점)

• 문제 설명
• 해결 과정
• 코드 전문

 

문제 설명

 

 

본 문제는 Leet Code 415번 문제로

음의 정수를 제외한 정수 두 개가 string 타입으로 주어지고, 이 두 string 타입의 정수(ASCII코드 상의 수)의

합을 구하여 string타입으로 반환하는 것이다.

 

이 문제는 string의 직접적인 정수형 형변환을 금합니다.

 

ex )

Input : num1 = "123" , num2 = "11"

Output : "134"

 

Input : num1 = "25" , num2 = " 133"

Output : "158"

 

 

해결 과정

 

 

 

내가 문제를 해결하면서 설계한 해결과정이다.

 

이 문제는 두 string이 주어지며 정수처럼 자릿수를 따지며 계산을 하여야 한다.

우선 두 string 중 자릿수가 더 큰 쪽을 찾아 longerStr으로 두고 짧은 쪽을 shorterStr으로 두었다.

(가장 큰 자릿수의 string의 길이만큼 반복문을 돌릴 것이기 때문이다.)

 

반복문에 들어가기 앞서 각 자릿수의 덧셈이 이루어질 때 사용될 sum 변수

carry 발생 시 carry 저장을 위한 carry 변수

최종합산 후 반환하기 위한 string의 resultStr까지 선언한다

이후 반복문에서 다뤄질 Index로는

longStrPValue와 shortStrPValue를 따로 두어 shortStr의 수가 다 읽혀진 뒤에도 longStr이 읽히도록 한다.

PValue는 Position value로 자릿수를 의미하며 각 각 longerStr.size()-1, shorterStr.size()-1로 

각 string의 끝인덱스(정수의 관점으로는 첫째 자리 수)로 초기화를 한다.

 

이제 이 문제의 핵심인 carry 발생 타이밍과 그에 따른 연산의 조건을 정의하여야 한다.

우선 긴 쪽의 str과 짧은 쪽의 str 둘 다 존재하는 자릿수까지 덧셈을 한다.

이 과정에서 두 str의 합이 9를 넘어서면 carry가 발생하며 

carry 변수를 1로 만들고 str의 합에서 ASCII코드 상 10만큼 빼준다.(*1 이 말이 좀 모호하게 들릴 수 있는데 밑에서 설명하겠다.)

 

이후 짧은 str 쪽이 먼저 끝나게 되고 긴 쪽의 str만이 자신의 수와 carry만을 합한다.

이렇게 매 반복마다 구해진 합을 반환 str에 넣는다.

 

마지막으로 긴쪽의 str의 길이만큼 반복되었음에도 불구하고

긴쪽의 str의 가장 큰 자릿수에서 carry가 발생할 수 있다.

그래서 긴쪽의 마지막 반복에서 carry가 발생했을 때

반환 str의 가장 큰 자릿수에 1을 넣는다.

 

ex )

Input : num1 = 999 , num2 = 1

num1.size = 3만큼 반복 시 Output : 000

3만큼 반복 후 carry가 1이라면 제일 큰 자릿수에 1을 넣어줌 Output : 1000

 

우리는 str의 가장 끝 인덱스(정수의 관점으로 첫째 자리 수)부터 접근하였기에

반환 str에는 숫자가 거꾸로 들어가 있을 것이다.

ex) 

Input : num1 = 11, num2 = 123

현재의 반환 str = 431  (우리의 기대는 134)

 

그렇기에 이 반환 str을 뒤집어 줘야 한다.

저는 여기서 <algorithm> 라이브러리의 reverse() 함수를 사용하였습니다.

이후 반환 str을 반환해줍니다. 

 

 

*1 ) 이다음에 볼 코드 전문에서는 str의 합에서 ASCII코드 상 10만큼 빼는 행위를 

subtractSumInCarry함수로 정의했다.

 

 

ASCII 코드 상에서 숫자들의 연산은 이러한 관계를 가집니다.

'0'을 나누는 이유를 한 문장으로 나타내자면

어느 문자숫자에도 연산이 가능한 상대적인 범위를 의미하기 위해서

문자숫자 이전의 문자와 문자 '0' 자신을 제외하는 것입니다.

 

subtractSumInCarry함수에서는 

sum -= '9' + '1' - '0' - '0'; 이라 정의되어있는데

첫 번째 '0'은 '9'와 '1'을 구하는 과정에서,

두 번째 '0'은 기존 sum과의 연산에서 사용되었습니다.

 

여기까지가 전체적인 문제해결의 과정입니다.

 

 

 

 

 

 

코드 전문

 

 

class Solution {
public:
    bool isOverCharNine(char& num)
    {
        if (num <= '9') return false;
        return true;
    }
    
    void subtractSumInCarry(char& sum)
    {
         sum -= '1' + '9' - '0' - '0';       
    }
    
    void calculSumAndCarryInCarry(char& sum, int& carry)
    
    {
            if (isOverCharNine(sum) == false)
            {
                 carry = 0;
            }
            else
            {
                 carry = 1;
                 subtractSumInCarry(sum);
            }
     }

    string addStrings(const string& num1, const string& num2) 
    {
        string longerStr;
        string shorterStr;
        if (num1.size() >= num2.size()) { longerStr = move(num1); shorterStr = move(num2); }
        else { longerStr = move(num2); shorterStr = move(num1); }

        char sum;
        int carry = 0;
        string resultStr;

        int longStrPValue = longerStr.size() - 1;  // PValue means Position value (자릿수)
        int shortStrPValue = shorterStr.size() - 1;
        for (;longStrPValue >= 0; longStrPValue--, shortStrPValue--)
        {
            if (longStrPValue >= 0 && shortStrPValue >= 0)
            {
                sum = longerStr[longStrPValue] + shorterStr[shortStrPValue] - '0' + carry;
                calculSumAndCarryInCarry(sum, carry);
            }
            else if (longStrPValue >= 0 && shortStrPValue < 0)
            {
                sum = longerStr[longStrPValue] + carry;
                calculSumAndCarryInCarry(sum, carry);
            }

            resultStr += sum;
        }        
        if (carry == 1) resultStr += '1';
        reverse(resultStr.begin(), resultStr.end());
        return resultStr;
    }
};

 

 

 

 

느낀 점 (잡설 97% , 배운점 3%(매우 많은 편))

 

이번 문제도 초급문제.. 허나 도중에 포기하고 다른 사람의 코드를 살짝 봤습니다. 대단하더군요.

링크 https://shareablecode.com/snippets/add-strings-c-solution-leetcode-kcYw-yCCj

제 코드보다 훨씬 매끄럽습니다. 그 분 코드에서는 나누기와 나머지 연산으로 carry를 다루고

그 carry를 이용해 sum을 또 구해냈습니다. 전 그 중 한 가지 정도에서만 포인트를 빌려 제 머리속에서 구상한

방법을 완성했네요. 다 만들고 나니 난해한거 같고 남한테 설명하기도 힘든 코드가 완성된거 같아 찝찝합니다.

 

물론 제 머릿속에서 구상한 방법을 완수했다는 점에서 상당히 뿌듯하고 지금까지 모호하게 다가왔던

컴퓨팅 사고라는 개념이 조금은 경험적으로 와닿은 순간이 아닌가 생각합니다.

특히 이번에 제가 생각해낸 방법은 아스키 코드를 가지고 다루는데 이게 정말 헷갈려서 여러 번의 시도가

필요하였습니다. 연산의 관점에서 숫자 0은 곱하거나 나누지 않는 이상 영향을 끼치지 않았는데

아스키코드 상에서는 '0' 그 자체로 자기 자리를 차지하고 있죠. 어떻게 범위를 정해야하지 여러 번 고민하다가 

답이 나왔습니다. 

그리고 함수 내부를 나누는 과정(제 나름의 리팩터링)을 하는데 calculSumAndCarryInCarry란 함수를 만들 때는 기절을 할 뻔 하였습니다. carry 발생시 sum과 carry에서 연산이 일어난다는 의미로 지었는데

참 이름이 모호한 것 같고 sum과  carry 연산 두 가지의 역할을 동시에 수행하는 것 같아

망설임이 느껴졌습니다. 다른 분들의 말씀 마냥 코드에 있어서 중요한건 가독성과 유지보수성이지

디자인패턴 그 자체에 너무 목 메는 것은 오히려 퇴보라하여 이 부분은 예의주시하며 앞으로 공부하려 합니다.

지금까지 string 문제를 두 가지 풀었는데 아직 string과 친해지기는 힘드네요.

오늘은 Algorithm 라이브러리의 reserve라는 함수를 사용하였습니다. 잘됐네요. 감사합니다.

 

 

 

긴 글 읽어주셔서 감사합니다. 

부족한 점이 있다면 부디 알려주시면 감사하겠습니다.