[python] 백준 13022 늑대와 올바른 단어

늑대와 올바른 단어

문제 이해는 참 쉽다.
풀면서 유용했던 주요 반례를 써 보았다.

주요반례

1. wolf					O
2. wolfwolf				O
3. wwoollff				O
4. wolfwwoollff			O
5. wolff				X
6. wolfwwww				X
7. wwoollffwwoollffw 	X

풀이

1.무작정 구현
모든 조건을 다 확인, w갯수를 stack개념으로 쌓기
그 후 다시 w가 나오면 또 stack을 쌓고 확인한다.
조건이 많았는데도 시간이 빨랐다.

import sys
input=sys.stdin.readline

st=input().rstrip()
if len(st)<4 or len(st)%4!=0 or st[0]!='w':
    print(0)
    exit()

now=0
stack=0
ans=1

def check():
    global now,stack,ans
    while now<=len(st):
        if st[now]=='w':
            if now+3>len(st):
                ans=0
                return
            stack+=1
            now+=1
            if now > len(st):
                return
        elif st[now]=='o' and stack==1:
            if st[now:now+3]=='olf':
                now+=3
                stack=0
                if now >= len(st):
                    return
            else:
                ans=0
                return

        elif st[now]=='o' and stack>1:
            if st[now:now+stack]=='o'*stack and st[now+stack:now+stack*2]=='l'*stack and st[now+stack*2:now+stack*3]=='f'*stack:
                now+=stack*3
                stack=0
                if now>=len(st):
                    return
            else:
                ans=0
                return
        else:
            ans=0
            return


check()
print(ans)

2. 효율적인 풀이법

백준에서 가장 깔끔한 코드 중 하나를 참고했다.
처음 봤을때 너무너무 이해가 안됐던 코드이다.
핵심은 while word와 word를 줄여나가며 갱신하는 것이 포인트이다 !!

쉽게 이해하자면,
i == 1이면 wolf
i == 2이면 wwoollff
....
i == 5이면 wwwwwooooolllllfffff
=> 정답이 되려면 for문을 반복하며 커지는 word중 일치하는 것이 무조건 있다!
앞에서부터 일치한다면 word를 갱신한다(줄여나감)

word = input()
def check(word):
    while word:
        for i in range(1, 13):
            if len(word) < 4*i:
                return 0
            if word[0:4*i] == 'w' * i + 'o' * i + 'l' * i + 'f' * i:
                word = word[4*i:]
                break
        else:
            return 0
    return 1

print(check(word))