[Python/파이썬] 백준 12933번 오리

12933번: 오리

 

문제

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

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

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

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

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

입력

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

출력

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

코드

처음 생각했던 풀이 (stack 이용) => 틀렸음

sound = list(input())
# 5의 배수가 아니면 quack이 안됨
if len(sound) % 5 != 0:
    print(-1)
    exit()
quack = ['q', 'u', 'a', 'c', 'k']
stack = []
for i in range(len(sound)):
    start = False
    # quack pop
    if sound[i] == 'k':
        idx = 3
        tmp = []
        start = True
        while stack:
            top = stack.pop()
            if top == quack[idx]:
                idx -= 1
                if idx == -1:
                    idx = 4
            else:
                tmp.append(top)
    else:
        stack.append(sound[i])

 

처음에는 위와 같은 방식으로 스택을 이용하여 풀이하려 했다. 이렇게 하면 문제점은 오리가 몇번 울었는지를 세는것이지 몇 마리의 오리가 울었는지는 셀 수 없다. 한마리가 여러 번 우는 경우를 못 센다는 말이다.

그래서 아예 방식을 바꿔서 아래와 같이 풀이했다.

 

정답 코드

sound = list(input())
# 5의 배수가 아니면 quack이 안됨
if len(sound) % 5 != 0:
    print(-1)
    exit()
quack = ['q', 'u', 'a', 'c', 'k']
visited = [False] * len(sound)
ans = 0
for i in range(len(sound)):
    if visited[i]:
        continue
    find = False
    if sound[i] == 'q': # quack 시작
        start = True
        idx = 1
        visited[i] = True
        for j in range(i+1, len(sound)):
            if sound[j] == quack[idx] and not visited[j]:
                visited[j] = True
                idx += 1
                if idx == 5:    # quack 완성
                    find = True
                    start = False
                    idx = 0 # 다시 q
        if find:
            ans += 1
        if start:   # 끝맺지 못한 quack이 있음
            print(-1)
            exit()
for i in range(len(visited)):
    if not visited[i]:
        print(-1)
        exit()
print(ans)

 

입력으로 들어온 문자열 sound를 하나씩 살펴보다가 q가 나오면 quack이 시작될 수 있으므로 그때부터 문자열 끝까지 탐색하며 quack을 나오는대로 visited 처리해준다. 끝까지 다 탐색해서 끝맺지 못한 문자열이 있는 경우는 올바르지 않은 소리이므로-1을 출력하고 프로그램을 종료시키고 그렇지 않고 quack이 하나라도 발견된 경우에는 ans의 값을 1 증가시켜준다.

만약 visited 배열에 하나의 원소라도 값이 False가 있다면 올바르지 못한 울음소리이므로 -1을 출력하고 프로그램을 종료시킨다. 그렇지 않다면 ans에 저장된 값을 출력한다.