[백준] 12933번번 (python 파이썬)

https://www.acmicpc.net/problem/12933

구현 문제이다.

 

울음소리를 보고 최소한의 오리가 몇마리인지 찾는다.

 

오리의 울음소리는 quack이다. q -> u -> a -> c -> k 를 순서대로 찾는다.

ex)

울음소리가 quqacukqauackck 라면

quack를 순서대로 찾는다.

quqacukqauackck

 

여기서 k 다음에 또 quack가 있다면 한마리의 오리가 연속으로 2번 소리를 낼 수 있다. (최소한의 오리 수를 찾아야 하기떄문에 중복가능)

quqacukqauackck

즉 한 오리가 이렇게 소리를 낸다.

방문한 문자는 visited 리스트를 만들어 방문처리를 한다.

 

다음 오리는(파란색)

quqacukqauackck

방문하지 않은 문자를 보고 quack를 찾는다.

 

녹음한 소리가 올바르지 않은 경우

- 문자열을 모두 방문을 하지 않았을때

- 오리가 0마리 일때

- 문자열의 길이가 5의 배수가 아닐때

 

 

첫 풀이

이전 문자를 저장하여 해당 문자를 비교해 나갔다.

duck = input()
visited = [False] * len(duck)
cnt = 0

if len(duck) % 5 != 0:
    print(-1)
    exit()


def solve(start):
    global cnt
    prev_s = None
    k_cnt = 0
    q_cnt = 0
    for i in range(start, len(duck)):
        if not visited[i] and duck[i] == 'q' and q_cnt == 0:
            visited[i] = True
            prev_s = duck[i]
            q_cnt += 1
            continue
        elif not visited[i] and duck[i] == 'q' and prev_s == 'k':
            visited[i] = True
            prev_s = duck[i]
            continue

        if not visited[i] and duck[i] == 'u' and prev_s == 'q':
            visited[i] = True
            prev_s = duck[i]
            continue

        if not visited[i] and duck[i] == 'a' and prev_s == 'u':
            visited[i] = True
            prev_s = duck[i]
            continue

        if not visited[i] and duck[i] == 'c' and prev_s == 'a':
            visited[i] = True
            prev_s = duck[i]
            continue

        if not visited[i] and duck[i] == 'k' and prev_s == 'c' and k_cnt == 0:
            visited[i] = True
            prev_s = duck[i]
            cnt += 1
            k_cnt += 1
            continue
        elif not visited[i] and duck[i] == 'k' and prev_s == 'c' and k_cnt > 0:
            visited[i] = True
            prev_s = duck[i]
            continue


for i in range(len(duck)):
    if duck[i] == 'q' and not visited[i]:
        solve(i)

if False in visited or cnt == 0:
    print(-1)
else:
    print(cnt)

 

 

두번째 풀이

quack문자를 만들어 q를 방문했으면 index를 증가시켜 다음 u를 비교하도록 하였다.

duck = input()
visited = [False] * len(duck)
cnt = 0

if len(duck) % 5 != 0:
    print(-1)
    exit()


def solve(start):
    global cnt
    quack = 'quack'
    j = 0
    first = True
    for i in range(start, len(duck)):
        if duck[i] == quack[j] and not visited[i]:
            visited[i] = True
            if duck[i] == 'k':
                if first:
                    cnt += 1
                    first = False
                j = 0
                continue
            j += 1


for i in range(len(duck)):
    if duck[i] == 'q' and not visited[i]:
        solve(i)

if not all(visited) or cnt == 0:
    print(-1)
else:
    print(cnt)