[BOJ / Python] 앵무새

 

 

🧩 문제 : 14713번 앵무새

 

💪🏻 문제 풀이 

첫번째 - 시간 초과

// 시간 초과
from collections import deque

N = int(input())
arr = list()

for i in range(N):
    arr.append(deque(map(str, input().split())))

sentence = deque(map(str, input().split()))


def is_possible(sentence, arr):
    k = 0
    while sentence:
        if arr[k] and sentence[0] == arr[k][0]:
            sentence.popleft()
            arr[k].popleft()
        k = (k + 1) % N

    if not sentence:
        return True
    else:
        return False


if is_possible(sentence, arr):
    print("Possible")
else:
    print("Impossible")

 앵무새가 말한 문장 N개와 상대방이 들은 문장을 queue에 저장한다. 

반복문으로 queue의 맨 앞에 있는 단어가 같다면 둘 다 pop해준다.

앵무새는 서로 말을 가로챌 수 있으므로 while문안에서 k = k + 1 % N으로 업데이트 해주면 계속 반복한다.

그리고 sentence가 모두 pop 되었으면 possible을 출력하고, sentence가 남아있다면 impossible을 출력하도록 했다. 

 

🥲 시간 초과 이유 

Impossible한 상황이라면 while문이 끝나지 않고 있었음 ..... 

 

 

두번째 - 틀렸습니다

// 틀렸습니다
from collections import deque

N = int(input())
arr = list()

for i in range(N):
    arr.append(deque(map(str, input().split())))

sentence = deque(map(str, input().split()))


def is_possible(sentence, arr):
    k = 0
    miss_cnt = 0
    while sentence:
        if arr[k] and sentence[0] == arr[k][0]:
            sentence.popleft()
            arr[k].popleft()
            miss_cnt = 0
        else:
            if miss_cnt == N:
                return False
            miss_cnt += 1

        k = (k + 1) % N

    if not sentence:
        return True
    else:
        return False


if is_possible(sentence, arr):
    print("Possible")
else:
    print("Impossible")

일치하지 않을 때 마다 miss_cnt를 1씩 증가시켜 miss_cnt가 N과 같아지면 False를 리턴하도록 했다.  

근데 왜 틀렷을까 ..

 

 

다른 풀이 참고 > 백준 채점 현황

from collections import deque

N = int(input())
arr = list()

for i in range(N):
    arr.append(deque(map(str, input().split())))

sentence = deque(map(str, input().split()))


def is_possible(sentence, arr):
    k = 0
    miss_cnt = 0
    while sentence:
        if arr[k] and sentence[0] == arr[k][0]:
            sentence.popleft()
            arr[k].popleft()
            miss_cnt = 0
        else:
            if miss_cnt == N:
                return False
            miss_cnt += 1
        k = (k + 1) % N

    empty = 0
    for i in range(N):
        if len(arr[i]) == 0:
            empty += 1

    if not sentence and empty == N:
        return True
    else:
        return False


if is_possible(sentence, arr):
    print("Possible")
else:
    print("Impossible")

앵무새가 말한 문장이 모두 비었는지 확인하니까 .. 됐음 ...

이 규칙 때문인 것 같다