[백준] 12933번 파이썬 - 오리문제

백준 12933

 

오리의 울음 소리가 주여지면, 몇 마리의 오리가 소리를 낸건지 최소 수를 구하는 문제이다.

quqacukqauackck

 

첫번째 오리는 "qu_ac_k_q_uack__"

두 번째 오리는 "__q__u__a____ck"

 

첫번째 풀이

시간 초과가 난 첫 번째 코드

오리 한마리당 문자열을 처음부터 끝까지 돌면서 quack를 찾는 방식으로 풀었다.

dfs 방법을 사용하여 시간초과가 난 것 같다.

 

str = list(input())
duck = ["q","u","a","c","k"]

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

def countDuck(n_str,str):
    idx = 0
    new_str = []
    if len(str) < 5:
        return n_str + str
   
    for i in range(len(str)):
        if str[i] == duck[idx]:
            idx += 1
            if idx==5:
                return(countDuck(n_str + new_str, str[i+1:]))
        else:
            new_str.append(str[i])
    return n_str + str

ans = 0
while len(str) >= 5:
    if len(str)== 5 and str != duck:
        ans = -1
        break
    num = countDuck([],str)
    ans += 1
    str = num

print(ans)

 

두번째 풀이

str = list(input())
duck = "quack"
cnt = 0
visited = [False] * len(str)

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

def countDuck(start):
    global cnt
    idx = 0
    is_right = True
    for i in range(start, len(str)):
        if str[i] == duck[idx] and visited[i] == False:
            visited[i] = True
            if duck[idx] == 'k':
                if is_right:
                    cnt += 1
                    is_right = False
                idx = 0 
            else:
                idx += 1

for i in range(len(str)):
    countDuck(i)

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

 

첫번째 풀이 방법처럼 string 자체 값을 변환하며 탐색하지 않고

visited 함수를 이용하여 코드를 짰더니 시간 초과 문제가 해결되었다.

 

12933번: 오리