C++로 알고리즘을 풀때 주의사항

S+='A'와 S=S+'A'의 차이

결론적으로 S+='A'를 사용해야 더 빠르다.

#include <iostream>
#include <string>
using namespace std;
int main() {
    string s;
    int n = 1000000;
    for (int i=0; i<n; i++) {
		s += "A"; }
	return 0; 
    }

S에 'A'를 100만번 추가하는 코드이며, 시간복잡도는 O(N)이 된다.

#include <iostream>
#include <string>
using namespace std;
int main() {
    string s;
    int n = 1000000;
    for (int i=0; i<n; i++) {
		s = s + "A"; }
	return 0; 
   }

반면 이 공식은 매번 새로운 문자열 S와 'A'를 더해주기 때문에, 시간복잡도는 O(N^2)이 된다.

 

* Java에서는 어떠한 방식을 사용하건 시간복잡도가 O(N^2)가 된다. 때문에 Stringbuilder를 이용해야한다.