jhko00   7년 전

괄호에 따라 여는 부분을 스텍에 넣고 

닫는 부분이 바로 다음 원소냐 아니냐를 따져

레이져와 파이프를 구분하고

레이져면 한번 자르니까 파이프에  +1

파이프면 이전 파이프의 값-1 (잘린 부분이 누적되므로)을 더해서

각 파이프 닫는 부분이 나오면 re 변수에 파이프 개수를 더하도록 짜봤습니다

원래 스텍에 있는 결과를 백터에 옮겨 파이프, 레이져를 구분해 연산하도록 했는데(주석 코드)

이중 반복문이 시간초과가 나서 고쳤는데도 시간초과가 납니다

그런데 문자열 길이만큼의 반복문만 돌렸음에도 다시 시간초과가 나는 원인이 안보입니다

어느 부분에 문제가 있는지 봐주시면 감사드립니다

jseo   7년 전

strlen 함수의 시간 복잡도는 O(n) 입니다.

jhko00   7년 전

jseo님 그러면 저 반복문 안에 있는 strlen함수만으로 시간 복잡도가 O(n)이 나온다는 말씀인가요?

jseo   7년 전

네, 그래서 총 시간 복잡도는 O(n^2)이 되겠죠. 

jhko00   7년 전

감사합니다 그 부분을 고려하고 다시 풀어봐야겠네요

댓글을 작성하려면 로그인해야 합니다.