[백준🥈3] #12933 오리 (Python)

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

12933번: 오리

 

문제

오리의 울음 소리는 "quack"이다. 올바른 오리의 울음 소리는 울음 소리를 한 번 또는 그 이상 연속해서 내는 것이다. 예를 들어, "quack", "quackquackquackquack", "quackquack"는 올바른 오리의 울음 소리이다.

영선이의 방에는 오리가 있는데, 문제를 너무 열심히 풀다가 몇 마리의 오리가 있는지 까먹었다.

갑자기 영선이의 방에 있는 오리가 울기 시작했고, 이 울음소리는 섞이기 시작했다. 영선이는 일단 울음소리를 녹음했고, 나중에 들어보면서 총 몇 마리의 오리가 있는지 구해보려고 한다.

녹음한 소리는 문자열로 나타낼 수 있는데, 한 문자는 한 오리가 낸 소리이다. 오리의 울음 소리는 연속될 필요는 없지만, 순서는 "quack"이어야 한다. "quqacukqauackck"과 같은 경우는 두 오리가 울었다고 볼 수 있다.

영선이가 녹음한 소리가 주어졌을 때, 영선이 방에 있을 수 있는 오리의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 영선이가 녹음한 소리가 주어진다. 소리의 길이는 5보다 크거나 같고, 2500보다 작거나 같은 자연수이고, 'q','u','a','c','k'로만 이루어져 있다.

출력

영선이 방에 있을 수 있는 오리의 최소 수를 구하는 프로그램을 작성하시오. 녹음한 소리가 올바르지 않은 경우에는 -1을 출력한다.

예제 입력 1

quqacukqauackck

예제 출력 1

2

예제 입력 2

kcauq

예제 출력 2

-1

예제 입력 3

quackquackquackquackquackquackquackquackquackquack

예제 출력 3

1

예제 입력 4

qqqqqqqqqquuuuuuuuuuaaaaaaaaaacccccccccckkkkkkkkkk

예제 출력 4

10

예제 입력 5

quqaquuacakcqckkuaquckqauckack

예제 출력 5

3

예제 입력 6

quackqauckquack

예제 출력 6

-1

 

✔️ Code

quack = 'quack'
duck = input()
visited = [0] * len(duck)

def find(start):
    global cnt
    j = 0
    first = 1
    for i in range(start, len(duck)):
        if duck[i] == quack[j] and not visited[i]: # 울음소리 비교
            visited[i] = 1
            if duck[i] == 'k':
                if first:
                    cnt += 1 # 오리가 연속으로 울면 한 마리로 치기 때문에 처음만 count 해줌
                    first = 0 # 똑같은 오리가 울 경우에 다음부턴 count 안해주기 위해서
                j = 0 # 마지막 문자인 k까지 나왔으면 다시 q부터 찾아서 비교해야 함
            
            else:
                j += 1 # k가 아니면 순서대로 다음 문자를 비교하기 위해 index ++

if len(duck) % 5 != 0: # 입력된 문자열의 길이가 5의 배수가 아니라면 올바르지 않은 울음소리임
    print(-1)
    exit() # -1을 출력하고 exit를 해주어야 프로그램이 종료되어 다음 for문 실행이 안됨

cnt = 0 # 오리의 수
for i in range(len(duck)):
    if duck[i] == 'q' and not visited[i]:
        find(i)

if cnt == 0 or not all(visited): # 오리의 수가 0마리거나 모든 문자를 방문하지 않았을 경우
    print(-1) # 올바르지 않은 울음소리

else: # 올바른 울음소리일 경우 오리의 수 출력
    print(cnt)

✏️ Comment

너무 어려움..
처음에 stack에다가 q나오면 u넣고 a넣고.. 이렇게 하면 될 줄 알고 호기롭게 짰는데 문제 이해를 잘못한 거였다.. ㅎㅎ;;;;
한참 고민해봐도 모르겠어서 구글링해서 참고하여 풀었음 ㅠㅠ 

주석에 설명을 자세히? 쓰려고 노력했다.
이 문제에서 중요한 부분들을 정리해봤다.

📌 한 마리의 오리가 연속으로 울 경우에는 한 마리만 세주고 더 이상은 'quack'가 나와도 더 세어주지 않는다.
first라는 변수를 두어 처음으로 quack이 완성되면 first = 0으로 바꿔주고 이 때만 cnt ++ 해준다.

📌 -1이 출력되는 조건들

1. 처음에 들어온 입력 문자열이 5의 배수가 아닐 때
   quack은 5글자이므로 입력이 5의 배수가 아니라면 오리의 수를 셀 수 없다. 따라서 올바른 울음소리가 아니다.
2. 오리의 수가 0마리일 때
   완전한 quack이 하나도 없다는 뜻이므로 올바른 울음소리가 아니다.
3. 모든 문자를 방문체크하지 않았을 때
   모든 문자를 다 체크하여 quack을 찾아서 오리의 수를 세어야하므로 모든 문자를 돌지 않았다는 것은 올바른 울음소리가 아니라는 뜻이다.

이게 실버3?!? 앞에 달팽이랑 별찍기도 모르겠어서 넘어오고 오리 문제 도전한 건데 얘도 어려웠다... ㅠㅠ... 구현문제 너무 어려웡