(python) 백준 알고리즘 9935번 - 문자열

백준 알고리즘 9935번 문제 - 문자열 폭발

사실 이 문제는 틀렸다. 문제 유출을 위해서 문제를 밝힐 순 없지만 제니퍼 소프트 문제와 약간 비슷한 측면이 있어서 풀어보았다. 물론 제니퍼는 DP를 썼어야 했지만 이건 아니다.

결론적으로 코드는 작성했지만 틀렸다.

그 이유는 시간초과였다. 이 모든 과정을 1초 내에 끝내야 하는데 DP를 사용하지 않은 탓인지 1,000,000의 문자열을 주었을 때 수행시간이 오버가 된다.

틀린 코드지만 올려보았다.

접근 방식

- 해당 문자열로 split을 한 후, join을 통해 새로운 문자열을 만든다.

- 해당 문자열이 있는 동안 loop를 돌린다.

- 남아 있는 문자열이 있는지 없는지를 체크한다.

코드 (python v2)

iStr = map(list, raw_input('input the first String : '))
fStr = map(list, raw_input('input the first String : '))
 
while fStr in iStr:
    iStr = "".join(iStr.split(fStr))
 
if iStr:
    print iStr
else:
    print "FRULA"