[백준] 1043번 거짓말 가능한 파티수 - set 활용

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

1043번: 거짓말

 

해당 문제를

각각의 파티를 m회차 점검하며, 진실을 듣게 될 사람을 추가하는 방식으로 구현하였다.

중복을 없애기 위해 extend와 set을 적절히 활용했고,

for party in party_list:

을 자주 활용했다.

 

 

1. List를 활용하여 구현(코드가 길고 가독성 떨어짐)

# BOJ_1043
def add_know_list(people_list):
    global known_list
    for person in people_list:
        if person in known_list:
            # 이 파티에서 진실을 들었으므로
            known_list.extend(people_list)
            # 중복 제거
            known_list = list(set(known_list))
            return True
        if person == people_list[-1]:
            return False


# 입력
n, m = map(int, input().split())
# 진실을 들은 사람 리스트
known_list = list(map(int, input().split()))
del known_list[0]
# 각 파티별로 참여자 리스트 저장
party_list = []
for _ in range(m):
    people_list = list(map(int, input().split()))
    del people_list[0]
    party_list.append(people_list)


# 1. 파티 m회차 점검: 진실을 듣게 될 사람 추가하기
# + 진실 말하는 파티 제거하기
for i in range(len(party_list)):
    for j in range(len(party_list)):
        if add_know_list(party_list[j]):
            party_list[j] = []
# 2. 남은 파티 갯수 세기
can_lie = 0
for party in party_list:
    if len(party) > 0:
        can_lie += 1
print(can_lie)

 

하지만 위에 코드에서 집합 set을 활용하면 더 간단한 코드를 만들 수 있을 것 같았다.

 

2. Set을 활용하여 구현(코드가 짧고 가독성 좋음)

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
knowList = set(input().split()[1:])
parties = []

for _ in range(m):
    parties.append(set(input().split()[1:]))

for _ in range(m):
    for party in parties:
        if party & knowList:
            knowList = knowList.union(party)

cnt = 0
for party in parties:
    if party & knowList:
        continue
    cnt += 1

print(cnt)

 

위 코드와 아래 코드의 차이는 아래와 같다. 

사용한 메모리는 같고 시간도 크게 차이 나지 않지만, 코드 가독성이 확실히 차이나는 것 같다.

 

 

---

얻어가고 싶은 점 1

if person in known_list:
    # 이 파티에서 진실을 들었으므로
    known_list.extend(people_list)
    # 중복 제거
    known_list = list(set(known_list))

이 코드를 

if party & knowList:
    knowList = knowList.union(party)

아래 처럼 간단 명료하게 대체할 수 있다는 점

union은 합집합을 구하는 set 연산자

 

set에 대한 다양한 연산자를 알고 싶다면 아래 클릭!

https://dojang.io/mod/page/view.php?id=2315 

파이썬 코딩 도장: 26.2 집합 연산 사용하기

 

얻어가고 싶은 점 2

# 진실을 들은 사람 리스트
known_list = list(map(int, input().split()))
del known_list[0]

0을 무시하고 1부터 입력 받고, 중복까지 제거하고 싶으면 아래처럼 코드를 구현할 수 있다는 점

knowList = set(input().split()[1:])

 

 

코드 출처 블로그:

https://ku-hug.tistory.com/148