LeetCode #415 AddStrings. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
한시간정도 걸린 듯? itos stoi 같은 이미 만들어진 변환 함수 쓰지 않고 푸는 문제
퍼포먼스랑 메모리 다 백프로 잘나옴
두 문자열 길이 비교 후 짧은 길이만큼 뒤에서부터 더해서 끝낼 수 있으면 끝내고,
끝나지 않으면 그 다음에 긴길이의 나머지 길이까지 가면서 확인했다.
Spent almost an hour? add two string integers without library function
Performance and Memory are both almost hundred percent
After comparing two strings, make returnString from back to short length first,
if it's still has overDigit, then check last long length numbers.
LeetCode #415
Q.
Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.
양의정수 num1 num2 가 문자로 주어지고, 해당 문자의 합을 구하라
Note:
The length of both num1 and num2 is < 5100.
Both num1 and num2 contains only digits 0-9.
Both num1 and num2 does not contain any leading zero.
You must not use any built-in BigInteger library or convert the inputs to integer directly.
노트 :
- 입력되는 문자 길이는 둘다 5100 안넘는다.
- 문자는 전부 0~ 9 까지 캐릭터만 가지고 있다.
- 0으로 시작하는 문자는 없다.
- 이미 있는 library 나 stream 등을 통해서 바로 integer 로 바꿔서는 안된다.
e.g.
There is no example, it's simple. Add two integer string without library
예제랄게 없음. 그냥 문자열로 된 정수 2개를 라이브러리 쓰지말고 더해서 출력해라.
Process
// Process
//1. Input two strings
//2. Set iteration length
//3. Make returnString using short string length
//4. Make returnString using last length, if it still has overDigit
//5. Return returnString(pointer)
// 처리과정
//1. 스트링 두개 입력받는다.
//2. 반복할 길이를 정한다. (짧은 것에 맞추어)
//3. 짧은 길이만큼 더해서 returnString 을 만든다.
//4. 나머지 길이만큼 returnString을 만든다 (자릿수 넘는 수가 있으면)
//5. 만들어진 returnString 을 반환한다.
Code.. lemme see example code!!!
코드.. 예제코드를 보자!!!
#include <iostream>
#include <string>
using namespace std;
// Process
//1. Input two strings
//2. Set iteration length
//3. Make returnString using short string length
//4. Make returnString using last length, if it still has overDigit
//5. Return returnString(pointer)
// 처리과정
//1. 스트링 두개 입력받는다.
//2. 반복할 길이를 정한다. (짧은 것에 맞추어)
//3. 짧은 길이만큼 더해서 returnString 을 만든다.
//4. 나머지 길이만큼 returnString을 만든다 (자릿수 넘는 수가 있으면)
//5. 만들어진 returnString 을 반환한다.
class Solution {
public:
string addStrings(string num1, string num2) {
string *returnString;
int n1 = num1.size();
int n2 = num2.size();
// Set length and Choose returnString
int length;
if (n1 >= n2)
{
length = n2;
returnString = &num1;
}
else
{
length = n1;
returnString = &num2;
}
// Make returnString till short input number
int overDigit = 0;
int int1;
int int2;
int sumNum;
for (int i = 1; i <= length; ++i)
{
int1 = num1[n1 - i] - 48;
int2 = num2[n2 - i] - 48;
sumNum = int1 + int2 + overDigit;
//cout << int1 << " " << int2 << " " << overDigit << " " << sumNum << " " << endl;
if (sumNum < 10)
{
returnString->at(returnString->size() - i) = (sumNum + 48);
overDigit = 0;
}
else
{
returnString->at(returnString->size() - i) = (sumNum + 38);
overDigit = 1;
}
}
if (overDigit == 1)
{
// Make returnString if it still have overDigit
length = abs(n1 - n2) - 1;
//cout << length << endl;
for (int i = length; i >= 0; --i)
{
int1 = returnString->at(i) - 48;
sumNum = int1 + overDigit;
cout << sumNum << endl;
if (sumNum < 10)
{
returnString->at(i) = (sumNum + 48);
overDigit = 0;
}
else
{
returnString->at(i) = (sumNum + 38);
overDigit = 1;
}
}
}
if (overDigit == 1)
returnString->insert(returnString->begin(), 49);
return *returnString;
}
};
int main(int argc, char *argv[]) {
string num1 = "9";
string num2 = "99";
Solution sln;
cout << sln.addStrings(num1, num2) << endl;
cout << 9 + 99 << endl;
}
Something else you might like...?
2019/02/13 - [Algorithm/Leet Code] - LeetCode #258 AddDigits. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/02/12 - [Algorithm/Leet Code] - LeetCode #136 SingleNumber. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/02/10 - [Algorithm/Leet Code] - LeetCode #171 ExcelSheetColumnNumber. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/02/09 - [Algorithm/Leet Code] - LeetCode #709 ToLowerCase. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/02/08 - [Algorithm/Leet Code] - LeetCode #400 NthDigit. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/02/03 - [Algorithm/Leet Code] - LeetCode #393 UTF-8 Validation. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/02/03 - [Algorithm/Leet Code] - LeetCode #398 RandomPickIndex. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/02/01 - [Algorithm/Leet Code] - LeetCode #905 SortArrayByParity. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/01/31 - [Algorithm/Leet Code] - LeetCode #593 ValidSquare. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/01/16 - [Algorithm/Leet Code] - LeetCode #217 ContainsDuplicate. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/01/21 - [Algorithm/Leet Code] - LeetCode #219 ContainsDuplicate2. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/01/22 - [Algorithm/Leet Code] - LeetCode #220 ContainsDuplicate3. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/01/23 - [Algorithm/Leet Code] - LeetCode #225 ImplementStackUsingQueue. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2018/10/19 - [Programming/Design Pattern ] - Design pattern - Prototype (디자인패턴 - 프로토타입) / Java C++ C#
2019/01/12 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #60 sudoku. Algorithm,알고리즘,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive
2019/01/12 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #59 spiralNumbers. Algorithm,알고리즘,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive
2019/01/08 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #58 messageFromBinaryCode. Algorithm,알고리즘,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive
2019/01/07 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #57 fileNaming. Algorithm,알고리즘,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive
2019/01/04 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #56 digitsProduct. Algorithm, 알고리즘, Codefights, CodeSignal, 코드파이트, 코드시그널, 예제,문제해결능력,example, c++ java c# scalar
2019/01/04 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #55 differentSquares. Algorithm, 알고리즘, Codefights, CodeSignal, 코드파이트, 코드시그널, 예제,문제해결능력,example, c++ java c# scalar
2018/12/28 - [Programming/Software Architecture] - Perfecting OO's Small Classes and Short Methods. 완벽한 객체지향의 작은 클래스와 짧은 메소드, Book:ThoughtWorks Anthology, Java,cpp,자바,oop,좋은코드,객체지향프로그래밍 - (#9, Tell, Don't Ask)
2018/12/26 - [Programming/Software Architecture] - Perfecting OO's Small Classes and Short Methods. 완벽한 객체지향의 작은 클래스와 짧은 메소드, Book:ThoughtWorks Anthology, Java,cpp,자바,oop,좋은코드,객체지향프로그래밍 (1)
2019/01/14 - [Programming/Java] - 자바 메모리 누수 체크/확인/고치는 방법, Memory leak check/fix in Java application, cleanCode/좋은코드/oop/객체지향
2019/01/25 - [Life/Health care] - L-Arginine 아르기닌 usage/side effects/dosage 효능/부작용/성인,소아 용법(3)
2018/12/16 - [Life/Health care] - L-Arginine 아르기닌 usage/side effects/dosage 효능/부작용/성인,소아 용법(2)
2018/12/27 - [Life/Health care] - Milk-Thistle 밀크시슬 usage/side effects/dosage/fatigue/supplement,효능/부작용/성인,소아 용법/건강/피로회복/영양제
2018/12/26 - [Life/Health care] - Selenium 셀레늄 usage/side effects/dosage 효능/부작용/성인,소아 용법