[LeetCode] 415. Add Strings

https://leetcode.com/problems/add-strings/

Add Strings - LeetCode

Add Strings.

 

올림픽을 보며 문제를 풀지 못한 지난 날들을 반성하며 올림픽 끝난김에 다시 꾸준히 풀기로 다짐했다.

Add String는 string으로 주어진 두 수를 더해 출력하는 문제다.

근데 그 수가 엄청 큰 수이므로 일반적인 integer로 표현할 수는 없고 string으로 표현해야 한다.

흔히 말하는 "Big Integer" 중 plus 를 구현하는 문제다.

악필로 풀이를 첨부해본다.

 

 

 

하나하나 살펴보자.

 

일반적인 덧셈연산은 뒤에서부터 진행하는게 편리하고, 출력은 앞에서 부터 해줘야하므로 stack을 생성해주자.

stack<char> st;

 

두 string이 같은 길이로 되어 있어야 편리하므로, 

짧은 string쪽의 앞에 0을 붙여준다.

 

while (num1.size() != num2.size()) {
	if (num1.size()>num2.size()) num2 = '0' + num2;
	else num1 = '0' + num1;
}

char를 int로 바꿀때는 ascii 코드값으로 바뀌므로 '0' 의 ascii 코드값을 빼주면 그 숫자가 된다.

반대로 int를 char로 바꿀때는 '0'을 더해주자.

 

뒤에서 부터 덧셈할때, 10이 넘어가면 앞자리수를 올려줘야하므로, 이를 저장할 temp 변수를 생성해준다.

int temp = 0;

 

이제 덧셈연산을 해주자.

길이를 똑같이 맞춰줬으므로, 뒤에서부터 똑같이 훑어주면 된다.

해당 위치 숫자를 각각 d1,d2 라 할때,

이 들을 int 로 먼저 바꿔주고,

두 숫자와 뒤에서 올라온 temp 를 더해 d3를 만들어 준다.

d3>9 일 경우, temp = 1이고 이외에는 0 인데, 이를 temp = d3/10으로 나타내주자.

이제 d3는 일의 자리만 필요하므로 temp*10을 빼줘야하고, char로 바꿔 stack에 넣어주면 된다.

for (int i=num1.size()-1; i>-1; i--) {
    int a = int(num1[i]) - '0';
    int b = int(num2[i]) - '0';
    int c = a+b+temp;
    temp = c/10;
    c -=temp*10;
    st.push(char(c+'0'));
}

 

마지막으로 제일 앞자리수를 더했을때 temp가 1이라면 temp도 넣어준다.

 

if (temp>0) st.push('1');

 

마지막으로 stack에서 하나씩 꺼내 출력해준다.

 

while (!st.empty()) {
    ret+=st.top();
    st.pop();
}

 

전체 코드는 아래와 같다.

 

class Solution {
public:
    string addStrings(string num1, string num2) {
        string ret = "";
        stack<char> st;
        while (num1.size() != num2.size()) {
            if (num1.size()>num2.size()) num2 = '0' + num2;
            else num1 = '0' + num1;
        }   
        int temp = 0;

        for (int i=num1.size()-1; i>-1; i--) {
            int a = int(num1[i]) - '0';
            int b = int(num2[i]) - '0';
            int c = a+b+temp;
            temp = c/10;
            c -=temp*10;
            st.push(char(c+'0'));
        }
        if (temp>0) st.push('1');
        while (!st.empty()) {
            ret+=st.top();
            st.pop();
        }
        return ret;
    }
};