[백준] 9935번 문자열 폭발 -python 파이썬 (시간초과 해결)
·
코딩테스트/백준
문제 이 문제에서 가장 유의해야할 점은 시간복잡도이다 왜냐하면 첫째줄에 주어지는 문자열의 길이의 범위가 굉장히 크기때문이다. (그래서 초반엔 시간복잡도 오류가 많이 발생함;;)먼저 이 문제를 어떤 알고리즘으로 풀어야할지 생각을 해본다면 단순히 폭발문자열이 들어가있는 때는 간단하지만 "CC44"처럼 연속해서 오는경우가 까다로워 진다. (while문으로 없을 때까지 확인하면 시간초과가 발생)그런데 이 문제 잘 생각해보면 괄호여닫기와 굉장히 유사하다는 것을 알 수 있다. 그래서 stack 을 사용하면 이 문제를 풀 수 있다. for 문으로 첫번째 문자열을 돌면서 폭발문자열이 들어가면 pop해주는 형식으로 구현해주면 된다. 이때 구현하면서 한가지 실수를 했는데 오답코드 string = input()b..