[BAEKJOON/Python] no.14713 앵무새 | Queue

문제

---

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

14713번: 앵무새

 

1차 풀이 : 구글링ㅎ

---

from collections import deque

bird_count = int(input())
bird_sentence_list = list()

for i in range(bird_count):
    bird_sentence_list.append(deque(map(str, input().split())))
sentence = deque(map(str, input().split()))

def possible(sentence, arr):
    misscount = 0
    j = 0
    while sentence:
        if arr[j] and sentence[0] == arr[j][0]:
            arr[j].popleft()
            sentence.popleft()
            misscount = 0 
        else:
            if misscount == bird_count:
                return False
            misscount += 1 
        j = (j + 1) % bird_count

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

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

if possible(sentence, bird_sentence_list):
    print("Possible")
else:
    print("Impossible")

👉🏻짠 전체코드는 다음과 같다. 한 줄씩 뜯어보도록 하자!

from collections import deque

bird_count = int(input())
bird_sentence_list = list()

for i in range(bird_count):
    bird_sentence_list.append(deque(map(str, input().split())))
sentence = deque(map(str, input().split()))

• 풀이에 필요한 deque를 import한다.
• 앵무새의 수를 bird_count에 앵무새가 말한 문장을 for문을 통해 deque형식으로 bird_sentence_list에 담는다. 
• 내가 받아 적은 문장을 sentence에 담는다.

#[
#   deque(['i', 'want', 'to', 'see', 'you']), 
#   deque(['next', 'week']), 
#   deque(['good', 'luck'])
# ]

👉🏻bird_sentence_list의 모습은 다음과 같다.

def possible(sentence, arr):
    misscount = 0
    j = 0
    while sentence:
        if arr[j] and sentence[0] == arr[j][0]:
            arr[j].popleft()
            sentence.popleft()
            misscount = 0 
        else:
            if misscount == bird_count:
                return False
            misscount += 1 
        j = (j + 1) % bird_count

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

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

👉🏻이제 앵무새가 한 말과 내가 적은 문장을 비교하는 possible 함수를 살펴보자!

• 새가 말한 문장의 단어와 내가 받아 적은 문장의 단어를 비교해서 불가능한 경우의 수인지 판단할 miscount와 새의 인덱스를 판별한 j라는 변수를 만들어준다.
• sentence가 빌 때까지 while문을 돌린다.
  • if문을 통해 현재 인덱스(j)의 새의 문장이 비어있지 않는지 확인하고, 새의 문장 첫 단어와 내 문장의 첫 단어를 비교한다.
  • 만약 단어가 같다면 각 deque의 첫 요소(같은 단어)를 제거하고 miscount를 0으로 설정한다. 틀린 경우의 수를 처음부터 다시 세기 위함이다.
  • 그렇지 않다면 miscount를 1만큼 올린다. 이 때 미리 miscount와 새의 수가 같은지 확인하고 같다면 모든 새를 다 확인했는데 모두 내 문장과 맞는 단어가 없었기 때문에 불가능한 경우리므로 바로 False를 return하며 함수를 끝낸다.
  • j의 인덱스를 +1해준다. 
• 새의 마리수만큼 for문을 돌려주면서 앵무새들이 들은 문장을 다 사용했는지 확인한다. 다 사용했다면 empty 변수에 +1해준다.
• 내가 적은 문장이 false 즉, 다 사용했고, 앵무새들의 문장도 다 사용했다면 True를 return하고 False를 return한다.