[백준/C++] 10757번: 큰 수 A+B

문제

두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 A와 B가 주어진다. (0 < A,B < 1010000)

출력

첫째 줄에 A+B를 출력한다.

풀이

브론즈지만 무턱대로 long long을 하면 바로 실패 뜨는 문제

1. string을 이용한 풀이

1) 자릿수 비교를 통해 A가 더 크도록 만들어주기

2) 자릿수 다르면 맞춰주기

3) 뒷자리부터 연산을 통해 string에 추가해준다.

4) 출력

#include <iostream>
#include <algorithm> // reverse
using namespace std;

int main(){
    // long long 자료형 길이 초과 -> string으로 받기
    string a, b;
    cin >> a >> b;

    int lenA = a.length();
    int lenB = b.length();

    // 01. 무조건 A 자릿수 크게 만들기
    if (lenB > lenA) {
        swap(a, b);
        swap(lenA, lenB);
    }

    // 02. 자릿수 다르면 맞춰주기
    // ex) 1234, 0032
    string tmp = "";
    if (lenA != lenB){
       for (int i=0; i<(lenA-lenB); i++)
           tmp += "0";
    }
    b = tmp+b;

    // 03. 뒷자리부터 하나씩 나눠서 answer에 추가
    string ans = "";
    int carry = 0; // 올림
    int x, y, digit; // 자리수
    for (int i=lenA-1; i>=0; i--){
        x = a[i] - '0';
        y = b[i] - '0';
        digit = x + y;
        if (carry == 1) {
            digit++;
            carry = 0;
        }
        if (digit > 9) // 반올림하는 경우
            carry = 1;
        ans += digit%10 + '0'; // to_string 사용 X
    }

    // 추가되는 한 자리 ex) 23+95 = (1)18
    if (carry == 1)
        ans += "1";


    // 1.1 리버스 함수 사용
//    reverse(ans.begin(), ans.end());
//    cout << ans;

    // 1.2 맨 뒤부터 거꾸로 출력(시간 복잡도 고려)
    for (int i=ans.length() - 1; i>=0; i--){
        cout << ans[i];
    }

}

 

2. stack을 이용한 풀이

1) 공통 부분 연산

2) a, b 중 남는 부분 연산(자릿수 다른 경우)

3) stack에 있는 것 출력

#include <iostream>
#include <stack>
using namespace std;

stack<int> calcPlus(string &a, string &b){
    stack<int> st;

    // 일의 자릿수
    int la = a.length() - 1;
    int lb = b.length() - 1;

    // 올림 여부
    bool carry = false;

    // 공통 부분 덧셈 연산
    while (la >= 0 && lb >= 0){
        int num = (a[la--] - '0') + (b[lb--] - '0');

        if (carry) // 이전 자릿수에서 올림된 경우
            num +=1;
        carry = num / 10; // 이번 자릿수에서 올림 여부 확인

        st.push(num % 10);
    }

    // a에서 남은 숫자 반영
    while (la >= 0){
        int num = a[la--] - '0';
        if (carry) // 이전 자릿수에서 올림된 경우
            num +=1;
        carry = num / 10; // 이번 자릿수에서 올림 여부 확인
        st.push(num % 10);
    }

    // b에서 남은 숫자 반영
    while (lb >= 0){
        int num = b[lb--] - '0';
        if (carry) // 이전 자릿수에서 올림된 경우
            num +=1;
        carry = num / 10; // 이번 자릿수에서 올림 여부 확인
        st.push(num % 10);
    }

    // 마지막 올림 확인
    if (carry)
        st.push(1);

    return st;
}

int main() {
    string a, b;
    cin >> a >> b;

    // 연산
    stack<int> st = calcPlus(a, b);

    while (!st.empty()){
        cout << st.top();
        st.pop();
    }
    cout << "\n";

    return 0;
}