[topcoder] WolfDelaymaster Algorithm

<Problem Link>


<Comment>

탑코더 문제는 일단 처음 풀어보는건데... 흠.. 홈페이지에서 컴파일 테스트가 불가능하다..
(그래서 실행시간도 없고, 내 풀이가 맞는지도 잘... 확신이 -ㅅ-...)

여튼,!! 생각보다 문자열이 꽤 단순한 패턴으로 들어와서 푸는것은 어렵지 않았다.
따로 정답 검증을 할수가 없으므로 혼자 test_case만들어서 점검하는 수밖에 -ㅅ-

어떻게 풀었는지 동작해보고 싶은분은 debug 주석을 제거하면 한눈에 보일것이다.

<Solution> Python - 내 생각엔 Accepted ..? ㅋㅋ

================================================
실행시간 : ???ms
시간복잡도 : O(N)
공간복잡도 : O(1)
================================================

def check(S):
if not S:
return "INVALID"

word = "wolf"
now_char_idx = 0
next_char_idx = 1
now_char_count = 1
full_char_count = 0

# check each string
for c in S:
# debugging log
#print "input[%s]:target[%s]:next[%s] // CNT[%s]:FCNT[%s]"%(c, word[now_char_idx], word[next_char_idx], now_char_count, full_char_count)

if c == word[now_char_idx]:
if now_char_idx == 0:
full_char_count += 1
else:
now_char_count += 1

elif c == word[next_char_idx]:
if next_char_idx == 0:
full_char_count = 1
now_char_count = 1
else:
if (now_char_count != 1):
if now_char_count != full_char_count:
# incorrect character count
return "INVALID"
now_char_count = 1

now_char_idx = next_char_idx
next_char_idx = (next_char_idx + 1) % 4
else:  # incorrect character order
return "INVALID"
# final check
if S.endswith("f") and (len(S)%4 == 0):
return "VALID"
else:
return "INVALID"

test_cases = [None,"","wolf", "wwwooolllfffwolfwwoollff","wolff", "wolfwwoollfff", "wwoollf", "wolfwolfowlf", "wwollff", "wolfwwoollffw"]
for case in test_cases:
print "INPUT [%s] :%s"%(case, check(case))



통계 위젯 (블랙)

15204
676
235520

GoogleAdsenseResponsive

Cluster map