4-L split 함수 사용 시 시간 초과

Question

강사님 안녕하세요, 4-L 문제 숫자 배열 입력받는 부분을 split 으로 구현을 해보았지만 시간초과가 발생을 해서요.. http://boj.kr/45ac0094d780431c9678842e88c8c48a 강사님 풀이와 같이 개별 char 에 대해 순차적으로 판단하여 바로 바로 container 에 push_back 하는 것이 확실히 더 빠를 것 같다고 생각은 됩니다.. split 함수 로직 자체가 token 을 만들어가면서 input string 에 대해 1회 탐색을 하게 되는 것이라 그렇게 오래 걸릴까? 싶긴한데요. string 에서 int 로 변환시키는 stol 함수가 문제인걸까요?

kundol · Answer

안녕하세요 ㅎㅎ 일단 로직 자체는 문제가 없습니다. split, reverse, size체킹, pop 로직 정말 잘 짜셨네요. 네 다만 split에서 그런 시간초과가 나는 거 같습니다. split을 잠깐보면 while ((pos = input.find(delimiter)) != string::npos) { token = input.substr(0, pos); ret.push_back(stoi(token)); input.erase(0, pos + delimiter.length()); } 이렇게 되어있습니다. find 자체의 시간복잡도가 O(N)이기 때문에 이를 계속해서 실행하기 때문에 최악의 경우 O(N^2) 정도가 되버리기 때문에 그러는 것 같습니다. 해당부분을 이렇게 한 번 바꿔 볼까요? for(char c : str_num){ if(c == '[' || c == ']') continue; // 숫자가 나오면 현재 수*10 한 뒤 더함 if(c >= '0' && c <= '9') x = x*10 + c-'0'; // 아닐 경우 현재 수를 덱에 넣음 else{ if(x > 0) numbers.push_back(x); x = 0; } } if(x > 0) numbers.push_back(x); 아 그리고 이 문제는 숫자 자체가 int형이 들어오기 때문에 ret.push_back(stoi(token)); 이렇게 쓰는 것이 좋습니다. 전체 코드는 다음과 같습니다. #include using namespace std; int T; // max 100 string p; // functions int N; // number of elements string str_num; deque split(string input, string delimiter) { // cout << "input = " << input << " "; deque ret; long long pos = 0; string token = ""; while ((pos = input.find(delimiter)) != string::npos) { token = input.substr(0, pos); ret.push_back(stoi(token)); input.erase(0, pos + delimiter.length()); } if (input.length() > 0) { ret.push_back(stoi(input)); } return ret; } int main(void) { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> T; while (T--) { deque numbers; bool error = false; bool dir = true; cin >> p; cin >> N; cin >> str_num; int x = 0; for(char c : str_num){ if(c == '[' || c == ']') continue; // 숫자가 나오면 현재 수*10 한 뒤 더함 if(c >= '0' && c <= '9') x = x*10 + c-'0'; // 아닐 경우 현재 수를 덱에 넣음 else{ if(x > 0) numbers.push_back(x); x = 0; } } if(x > 0) numbers.push_back(x); for (char func : p) { if (func == 'R') { dir = !dir; } else if (func == 'D') { if (numbers.size()) { if (dir == true) { numbers.pop_front(); } else { numbers.pop_back(); } } else { error = true; break; } } } if (error) { cout << "error "; } else { if (dir == false) { reverse(numbers.begin(), numbers.end()); } cout << "["; for (int i = 0; i < numbers.size(); ++i) { cout << numbers[i]; if (i < numbers.size() - 1) { cout << ","; } } cout << "] "; } } return 0; } 감사합니다.

gdgd · Answer

split의 시간 복잡도는 n인것 같은데, 왜 최악의 경우일때, n^2인가요?