1874 백준

문제가 명확한 만큼 그냥 stack을 이용하여 top과 input이 다르면 다음 순서의 번호를 push하고, 같다면 pop을 하여 풀어서 해결하면 되는 문제였다.

 

그런데 시간초과가 나서 이상하다고 생각하고 고민해봤었는데 아무리 생각해도 push는 최대 10^5만큼만 발생할 것이고 pop도 같은 수만큼 발생할 것이라고 생각했다. stack에서는 이것들이 O(1)이니까 문제가 일어나는 부분이 절대 아니라고 생각해서 output을 담당하는 string에 의심을 하기 시작했다.

 

나는 string을 갱신하기 위해서 append를 사용했는데, 이전에 vector에서 insert와 erase와 같은 함수 자체의 복잡도가 상수가 아닌 경우를 의심했고, 찾아보니 역시나였다 

append를 push_back과 같이 문자열을 그냥 concat하는 것과 같으므로 기존의 문자열의 길이를 N, 붙일 문자열의 길이를 M이라고 했을때 복잡도를 O(M)이라고 예상했으나, 새로운 문자열을 만들고 그 문자열을 리턴하는 함수이므로 O(N+N이었다.

이후 append를 push_back으로 대체하고 제출하니 문제없이 풀렸다.

STL에서 제공하는 함수들 중, 추가, 삭제의 복잡도에 대해서 다시한번 생각해보는 계기가 되었다.