[Python/코테] 백준 12933 오리

12933 오리

문제 및 조건 설명: https://www.acmicpc.net/problem/12933

알고리즘 설계

💡idea.

눈으로는 판단하기 쉽지만, 코드 작성은 복잡한 구현 문제이다. 

 

🎲step.

1. 잘못된 울음소리의 경우를 정의한다. 

2. 한 마리로 세는 단계는 다음과 같다.

1. 'q' 로 울면, 한 마리의 울음소리 검사를 시작한다.
2. 'u', 'a', 'c', 로 운다. 
3. 'k' 까지 운다. 한 마리로 간주한다.

3. 이 때, 3번이 되기 전에 1-2번이 시작된다면 다른 오리로 간주해서, 오리의 갯수를 증가시켜 주어야 한다. 'k'까지 다 울고 다시 시작되는 'q'는 한 마리의 오리가 두 번째 울기 시작한 것일 수 있다.   

 

알고리즘 구현

코드 출처: https://yuna0125.tistory.com/179

import sys

sound = sys.stdin.readline().strip()
answer = 'quack'
visited = [False] * len(sound)

cnt = 0
start = 0


def find_duck(start):
    global cnt
    j = 0       # 'quack' 문자 검사용 인덱스
    first = 1   # 한 번 quack 운 오리는, 갯수에 카운팅x

    for i in range(start, len(sound)):
        if sound[i] == answer[j] and not visited[i]:
            visited[i] = 1

            if sound[i] == 'k':
                if first:
                    cnt += 1
                    first = 0
                j = 0
            else:
                j += 1


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

for i in range(len(sound)):
    if sound[i] == 'q' and not visited[i]:
        # 울음소리가 시작되었고, 검사한 적 없는 오리이면
        find_duck(i)

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

나다어

• 반복되는 코드는 함수로 만들자.
  그러다 함수가 겹쳐서 값이 중복될까 걱정된다면, visited 배열과 같이 flag 변수를 두자. 
• input() 은 sys.stdin.readline() 과 달리 입력완료 후의 엔터(개행문자)를 삭제하고 저장한다.
  input() 과 같은 내용을 저장하기 위해서는 sys.stdin.readline().strip() 로 해주어야 한다.