🧩 문제 : 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")
앵무새가 말한 문장이 모두 비었는지 확인하니까 .. 됐음 ...
이 규칙 때문인 것 같다
'알고리즘' 카테고리의 다른 글
[프로그래머스 / Python] 체육복 (1) | 2023.02.05 |
---|---|
[BOJ / Python] 1107 리모컨 (0) | 2023.02.04 |
[BOJ / Python] 1484 다이어트 (0) | 2023.01.30 |
[BOJ / Python] 1325 효율적인 해킹 (1) | 2023.01.24 |
[BOJ / Python] 2156 포도주 시식 (0) | 2023.01.20 |