백준 알고리즘 9935번 문제 - 문자열 폭발
사실 이 문제는 틀렸다. 문제 유출을 위해서 문제를 밝힐 순 없지만 제니퍼 소프트 문제와 약간 비슷한 측면이 있어서 풀어보았다. 물론 제니퍼는 DP를 썼어야 했지만 이건 아니다.
결론적으로 코드는 작성했지만 틀렸다.
그 이유는 시간초과였다. 이 모든 과정을 1초 내에 끝내야 하는데 DP를 사용하지 않은 탓인지 1,000,000의 문자열을 주었을 때 수행시간이 오버가 된다.
틀린 코드지만 올려보았다.
접근 방식
- 해당 문자열로 split을 한 후, join을 통해 새로운 문자열을 만든다.
- 해당 문자열이 있는 동안 loop를 돌린다.
- 남아 있는 문자열이 있는지 없는지를 체크한다.
코드 (python v2)
1 2 3 4 5 6 7 8 9 10 | 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" | cs |
'Data Engineer > Algorithm' 카테고리의 다른 글
(python) 백준 알고리즘 1924번 (0) | 2016.05.03 |
---|---|
(python) 백준 알고리즘 11727번 - Dynamic Programming (1) | 2016.05.03 |