[Silver II] 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

---

# 풀이 방법

duck_crying 리스트를 돌면서 바로바로 체크하는 방법으로 코드를 구현할 수 있다.

quack = "quack'이라고 정의하고

ongoing 리스트를 만들어 하나씩 추가하는 방식이다.

 

이렇게 구현하고 싶었지만 아이디어가 떠오르지 않아 다른 풀이로 접근했던건데

잘 기억해놔야겠다.

---

# 코드

import sys
sys.stdin = open("input.txt","r")

duck_crying = list(sys.stdin.readline().strip())

# 올바른 울음 순서
quack = "quack"
ongoing = []  # 진행 중인 quack 상태들

for ch in duck_crying:
    placed = False
    for i in range(len(ongoing)):
        idx = ongoing[i]
        if ch == quack[(idx + 1) % 5]:  # 다음 문자와 일치하면
            ongoing[i] = (idx + 1) % 5
            placed = True
            break
    if not placed:
        if ch == 'q':
            ongoing.append(0)
        else:
            print(-1)
            sys.exit()
    print(ongoing)

# 모든 울음은 "k"에서 끝나야 함 (quack의 마지막 문자)
if all(x == 4 for x in ongoing):
    print(len(ongoing))
else:
    print(-1)

---

# 참고

첫 시도.. 틀린 코드라고 하는데 이유를 모르겠음 입력 예시가 다 맞는데

<방법>

일단 울음 소리의 시작인 q의 위치를 찾는다.

그리고 각각의 울음 소리마다 (시작위치=q, 끝 위치=k)를 저장한다.

이 울음 소리가 겹치면 오리의 수가 증가하고, 그렇지 않을 경우에는 이전의 동일한 오리라고 판단한다.

# 2025-05-04 18:46-
import sys
sys.stdin = open("input.txt","r")

duck_crying = list(sys.stdin.readline().strip())
position_q = [] # q의 시작 위치저장
quack_list = [] # quack의 

for i in range(len(duck_crying)):
    if duck_crying[i] == 'q':
        position_q.append(i)

for pq in position_q:
    tmp_list = ['q']
    duck_crying[pq] = '*'
    for i in range(pq+1,len(duck_crying)):
        if len(tmp_list) == 1 and duck_crying[i] == 'u':
            duck_crying[i] = '*'
            tmp_list.append('u')
        elif len(tmp_list) == 2 and duck_crying[i] == 'a':
            duck_crying[i] = '*'
            tmp_list.append('a')
        elif len(tmp_list) == 3 and duck_crying[i] == 'c':
            duck_crying[i] = '*'
            tmp_list.append('c')
        elif len(tmp_list) == 4 and duck_crying[i] == 'k':
            duck_crying[i] = '*'
            quack_list.append((pq,i))
            break

if len(quack_list)*len('quack') != len(duck_crying):
    print(-1)
else:
    cnt_duck = 1
    for i in range(1, len(quack_list)):
        pq1, pk1 = quack_list[i-1]
        pq2, pk2 = quack_list[i]

        if not pk1 < pq2:
            cnt_duck += 1
        
            for j in range(i-1,-1,-1):
                pq3, pk3 = quack_list[j]
                if pk3 < pq2:
                    cnt_duck -= 1
                    break

    print(cnt_duck)