시뮬레이션 문제나 계산량이 많은 문제에 약점이 있다고 생각해서 풀었던 문제이다. 사실 계산량적인 부분에서 고전하진 않았지만, 문제이해가 다소 어려웠던 문제이다.
정답률이 30% 로 낮은 편에 속하는데 많은 사람들이 같은 이유로 많이 틀렸던 것 같다.
문제 이해 및 적용하기
이 문제는 사람 수 N과 파티의 수 M을 입력 받고 난 다음에 각 파티당 좋아하는 이야기를 하는데 과장을 할 수 있는 경우의 수를 구한다.
여기서 가장 중요한 사실은 (높은 오답률의 요인) 문제에서 주어진 증인만 고려해서 사실을 전달한다고 생각해주면 안된다.
증인과 같은 그룹에 있었던 사람들도 사실인 이야기를 듣는데 다른 그룹에서 과장된 이야기를 들으면 거짓말쟁이가 되기 때문이다.
그리고 그 deque가 비어질 때까지 증인들을 각 그룹별로 들어있는지 확인하는 식으로 그룹별로 순회하면서 확인하였는데.
위에서 말한 내용을 적용해주기 위하여 증인과 같은 그룹에 있었던 사람들도 증인들도 순회하면서 증인 deque에 넣어주었다.
# check for each groups
lierState = []
for i in range(m):
lierState.append([])
ans = 0
alreadyLied = []
while(len(liers) != 0):
curLier = liers.popleft()
alreadyLied.append(curLier)
for i in range(m):
if curLier in group[i][1:]:
lierState[i].append(True)
for j in range(len(group[i])-1):
curPerson = group[i][j+1]
if (not curPerson in alreadyLied) and (not curPerson in liers):
liers.append(curPerson)
else:
lierState[i].append(False)
해당 설명에 대한 코드는 다음과 같다. 증인들의 그룹을 Lier deque라고 명명한 것을 양해해주길 바란다.
그리고 각각의 그룹별로 증인들이 있는지 확인하는 list를 lierState로 지정하였다.
최종적으로 각 그룹별 lierState가 모두 False이면 (증인들이 그 그룹내에 아무도 없으면) answer count를 늘려주었다.
for i in range(m):
if True in lierState[i]:
continue
else:
ans += 1
print(ans)
주의할 점
증인과 같은 그룹에 있었던 사람들도 사실인 이야기를 듣는데 다른 그룹에서 과장된 이야기를 들으면 거짓말쟁이가 되기 때문이다
본인은 deque를 증인들을 넣어주면서 순회하였지만, set을 통한 풀이도 많이 보였다.
전체코드
import sys
from collections import deque
input = sys.stdin.readline
# group & lier List
n, m = map(int,input().split())
liers = deque(map(int,input().split()))
liers.popleft()
group = []
for i in range(m):
group.append(list(map(int,input().split())))
# check for each groups
lierState = []
for i in range(m):
lierState.append([])
ans = 0
alreadyLied = []
while(len(liers) != 0):
curLier = liers.popleft()
alreadyLied.append(curLier)
for i in range(m):
if curLier in group[i][1:]:
lierState[i].append(True)
for j in range(len(group[i])-1):
curPerson = group[i][j+1]
if (not curPerson in alreadyLied) and (not curPerson in liers):
liers.append(curPerson)
else:
lierState[i].append(False)
for i in range(m):
if True in lierState[i]:
continue
else:
ans += 1
print(ans)