백준 12933: 오리 (Python)

 

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

12933번: 오리

 

 

로직은 이러함..

이때까지만 해도 쉬운 문제인 줄 알았지..

 

첫 시도 (실패)

sound를 차례대로 순회하면서

q -> u -> a -> c -> k 에 해당하면 넘어가고, 해당하지 않으면 temp 배열에 문자를 넣는다.

순회가 끝난 후 sound와 temp가 같다면 (q-u-a-c-k를 찾지 못한 경우) break해주고,

같지 않다면 sound = temp 후 정답을 하나씩 추가했다.

sound = input()

duck = ['q', 'u', 'a', 'c', 'k']
answer = 0

while sound:
    temp = []
    pos = 0
    for s in sound:
        if s == duck[pos]:
            pos += 1
            if pos > 4:
                pos = 0
        else:
            temp.append(s)
    
    if sound == temp:
        answer = -1
        break

    sound = temp
    answer += 1

print(answer)

반례) quackq -> -1 출력 (내 코드는 1 출력)

 

두 번째 / 세 번째 시도 (시간 초과)

sound의 길이가 5의 배수가 아닌 경우 break문을 걸어주는 걸로 수정했다.

나머지는 위랑 동일

sound = input()

duck = ['q', 'u', 'a', 'c', 'k']
answer = 0

while sound:
    if len(sound) % 5 != 0:
        answer = -1
        break

    temp = []
    pos = 0

    for s in sound:
        if s == duck[pos]:
            pos += 1
            if pos > 4:
                pos = 0
        else:
            temp.append(s)

    sound = temp
    answer += 1

print(answer)

거의 끝까지 채점하길래 통과되는 줄 알았으나 95%에서 시간 초과함..

 

시간 조금이라도 줄여보겠다고

len(sound)를 매 반복문마다 호출하지 않고,

size = len(sound) 변수를 선언해주고 s == duck[pos]일 때 size 하나씩 감소시키도록 수정했는데

똑같이 95%에서 시간 초과했다.

 

네 번째 시도 (성공)

visited 배열을 선언하고(False), q - u - a - c - k 순서대로 만날 때마다 True로 바꿔줬다.

매 반복문마다 visited=True이면 비교하지 않고 넘어가도록 했다.

 

total, cnt 변수를 선언해주고

cnt - 각 반복문에서 방문한 문자열의 개수

total - 모든 반복문에서 방문한 문자열의 개수의 총합

 

while문 조건을 total < len(sound)로 잡아주고

(모든 문자열을 다 자르면 종료)

cnt가 5의 배수가 아니거나(quack 중간에서 잘린 경우), 0일 때(자른 문자열이 없는 경우)

break문을 걸어줬다.

 

sound = input()

duck = ['q', 'u', 'a', 'c', 'k']
visited = [False] * len(sound)
total = 0
answer = 0

while total < len(sound):
    temp = []
    cnt = 0
    pos = 0

    for i in range(len(sound)):
        if visited[i]:
            continue

        if sound[i] != duck[pos]:
            continue
      
        visited[i] = True
        cnt += 1
        total += 1

        pos += 1
        if pos > 4:
            pos = 0
    
    if cnt % 5 != 0 or cnt == 0:
        answer = -1
        break

    answer += 1

print(answer)

드디어... 통과했다..

진짜 풀다가 홧병 날 뻔 ㅜㅜㅜ