chkwon91   1년 전

읽어들인 문자열에서 글자 한 번씩만 검사하는 방법을 사용했습니다.

stack 개념을 사용하지 표준 라이브러리는 사용하지는 않았구요..

stack top에 있는 문자와 현재 문자가 동일하면 pop을 그렇지 않으면 push하고

문자열을 모두 읽고 나서 stack size가 0이면 가능한 단어로 판단했습니다.

단어를 한 번은 스캐닝 하도록 했습니다.. 그런데 시간초과가 뜨네요... 시간복잡도는 O(N)인데 시간초과가..

도대체 푸신분들은 어떻게 푸신건가요..? 단어를 다 훑지도 않고 푸신건가요? ㅠ

baekjoon   1년 전

for 안에 strlen(s)를 쓰면, 매번 strlen(s)를 구하게 됩니다.

즉 시간 복잡도는 strlen(s)의 제곱이 됩니다.

int len = strlen(s); 와 같이 변수로 따로 만들어주는 것이 좋을 것 같습니다.

chkwon91   1년 전

아 그렇군요! 그동안 몰랐습니다 ㅠㅠㅠ

AC 받았습니다 감사합니다!

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