[BOJ][⚪2][백준#13022] 늑대와 올바른 단어

문제 출처

BAEKJOON Online Judge #13022

문제

다음은 늑대 나라에서 사용하는 올바른 단어에 대한 설명이다.

임의의 양의 정수 n에 대해서, ‘w’가 n번 나오고, 그 다음에 ‘o’가 n번, 그 다음에 ‘l’이 n번, 그 다음에 ‘f’가 n번 나온 단어는 올바른 단어이다. 올바른 단어 두 개를 이은 단어도 올바른 단어이다. 1번과 2번 조건으로 만들 수 있는 단어만 올바른 단어이다.

다음은 올바른 단어의 예시이다.

1번 규칙으로 만든 “wolf”, “wwoollff”, “wwwooolllfff”는 모두 올바른 단어이다. 2번 규칙으로 만든 “wolfwwoollff”은 올바른 단어이다. 2번 규칙을 두 번 써서 만든 “wolfwwoollffwolf”은 올바른 단어이다. “wfol”은 올바른 단어가 아니다. (순서가 올바르지 않음) “wwolfolf”는 올바른 단어가 아니다. (문자열의 중간에 다른 문자열을 집어 넣음) “wwwoolllfff”는 올바른 단어가 아니다. (o가 2번 들어갔다)

입력

첫째 줄에 단어가 주어진다. 단어는 w, o, l, f로만 이루어져 있으며, 길이는 50을 넘지 않는다.

출력

입력으로 주어진 단어가 올바른 단어인 경우에는 1을, 아니면 0을 출력한다.

예제

예제 1

입력

wolf

출력

1

예제 2

입력

wwolfolf

출력

0

My Sol

def main():
    def check_main():
        pl = check_len_per_part(i)
        if i+pl*4 > tl: return False
        for j in range(1, 4):
            if check_per_part(i+pl*j, pl, list('wolf')[j]): continue
            return False
        return pl*4

    def check_len_per_part(ii):
        pl = 0
        while ii < tl and txt[ii]=='w':
            pl += 1
            ii += 1
        return pl

    def check_per_part(si, pl, c):
        for pi in range(pl):
            if txt[si+pi] == c: continue
            return False
        return True

    txt = input()
    if txt[0] != 'w': return 0
    tl = len(txt)
    i = 0
    while i < tl:
        check_ret = check_main()
        if not check_ret: return 0
        i += check_ret
    return 1

print(main())

함수로 구분하여 쉽게 풀 수 있는 문제였다. 문제 풀이의 컨셉은 분할과 정복이다. 즉, 전체 단어는 wwwooolllfff 와 같이 w,o,l,f가 같은 개수로 반복되는 단어와, 이들의 연결로 되어있기 때문에 w를 맞이한 순간부터 wolf단어를 판단하고, 만족한다면 넘어가면서 확인하면 되겠다.

1. main 함수에서 입력을 처음 받는데, 만약 처음 시작이 w로 시작하지 않는다면 무의미하므로 분기처리해주었다.
2. 각 wolf 단어의 첫 인덱스를 i라고 생각하겠다. txt의 길이 tl보다 i가 작은 경우에만 wolf 단어 판독의 확인을 하는데, 이를 check_main 함수에서 해주었다.
3. check_main 함수에서는 w의 단어 길이를 재는 check_len_per_part 함수로부터 각 연속단어의 길이 pl을 구하고, 이 각 부분의 4배, 즉 wolf단어를 모두 확인하는 과정에서 인덱스가 전체 길이를 넘어가는지 확인한다. 만약 넘어간다면 wolf 단어 생성 자체가 안되므로 버린다.
4. wolf 단어의 각 문자 각각의 인덱스로부터 단어가 맞는지 확인한다.
5. 모두 맞다면 True를 return하고 아니라면 False를 return한다.
6. main에서 이를 모두 확인하여 wolf 단어 확인하는 check_main 함수에서 모두 True라면 1을, 아니라면 0을 반환한다.
7. 이를 출력한다.

결과

맞았습니다!!

이번 문제 풀이는 전체 77개의 파이썬3 풀이 중에 연산시간 공동 1등을 기록한 풀이였으며, 개인적으로는 36ms의 연산시간 풀이를 본 적이 없는 터라 신기했던 풀이여서 풀이를 남긴다.