[백준] 1043번 거짓말 _ Python

2024. 2. 20. 15:33·Algorithms/Data Structure

[초기 접근 방법]

- 맨 처음에 제시한 사람은 무조건 "진실"만을 들어야 한다.
- 각 사람마다 일관되게 "과장된 이야기 or 진실"을 들어야 한다.
- 해당 파티에서는 무조건 "과장된 이야기 or 진실"을 이야기해야 한다.

1. 제시한 사람이 있는 파티는 일단 전부 진실을 말한다.
2. 위 파티에 있는 사람들 모두 "진실파티" 에 넣는다.
3. 각 파티를 탐색하면서 파티 참석 인원 중
    "진실파티"에 있는 사람이 있다면 참가한 사람들을 "진실파티"에 추가를 하고, 파티를 처음부터 다시 탐색해야 한다.
    "진실파티"에 있는 사람이 없다면 해당 루프에서 종료한다.

 

 

 

[생각]

1. input.split() 내에서의 슬라이싱

set(map(int, input().split()[1:]))

 

 

2. set.union()

 

list의 extend() 처럼 두 set 을 합집합 할 수 있다.

knowList = knowList.union(party)

 

 

3. set 연산자

 

| (합집합)

     s1.union(s2)
& (교집합)

     s1.intersection(s2)
- (차집합)

     s1.difference(s2)
^ (합집합-교집합)

     set.symmetric_difference(s1, s2)

 

# party에 knowList 원소가 있는지 판별하는 방법

# 1)
for know in knowList:
    if know in party:
        cnt1 += 1

# 2)
if knowList & party:
    cnt2 += 1

 

 

+. 이외에도 각 파티의 참가 인원들을 노드로 연결지어 그래프 탐색으로 풀 수도 있다.

 

 

[코드]

1. for 문으로 일일이 knowList를 갱신하는 코드

# 구현

# 풀이 시간 : 30분
# 시간복잡도 : O(M * a)
# 공간복잡도 : O(M or N)
# 참고 : -

import sys
input = sys.stdin.readline

# 사람의 수, 파티의 수
N, M = map(int, input().split())

# 진실을 아는 사람의 수, 번호가 주어짐
knowList = list(map(int, input().split()))
knowList.remove(knowList[0])
knowList = set(knowList)

# 각 파티에 오는 사람의 수, 번호
partyList = [list(map(int, input().split())) for _ in range(M)]

# 각 파티에서 거짓말을 할 수 있는지를 체크할 수 있는 리스트
# True : 거짓말 가능 / False : 진실만을 말함
visitedLie = [False] * M

while True:
    knowListLength = len(knowList)

    # 모든 파티 탐색
    for i in range(M):
        addTrue = False
        # 각 파티에 "진실 파티원"이 있는지 탐색
        for j in range(1, len(partyList[i])):
            # "진실 파티원"이 있을 경우 "진실파티"에 추가
            if partyList[i][j] in knowList:
                for k in range(1, len(partyList[i])):
                    knowList.add(partyList[i][k])
                addTrue = True
                break

        # 추가되었음을 flag → 해당 파티에서는 진실만을 말해야한다.
        if addTrue:
            visitedLie[i] = False

        # "진실 파티원"이 없기 때문에 해당 파티에서는 거짓말을 말해도 된다.
        else:
            visitedLie[i] = True

    # 모든 파티를 탐색했음에도 더 이상 "진실파티"가 갱신이 되지 않는 경우 탐색을 종료한다.
    if knowListLength == len(knowList):
        break


# 거짓말을 해도 되는 파티 개수를 출력한다.
result = 0
for i in range(M):
    if visitedLie[i]:
        result += 1

print(result)

 

 

 

2. & 연산자와 flag 없이 간결히 한 코드

import sys
input = sys.stdin.readline

# 사람의 수, 파티의 수
N, M = map(int, input().split())
# 진실을 아는 사람의 수, 번호가 주어짐
knowList = set(map(int, input().split()[1:]))
# 각 파티에 오는 사람의 수, 번호
partyList = [set(map(int, input().split()[1:])) for _ in range(M)]

for _ in range(M):
    for party in partyList:
        # 파티 참석자 중에 진실을 알고 있는 사람이 있다면
        if knowList & party:
            knowList = knowList.union(party)

trueParty = 0
for party in partyList:
    for know in knowList:
        if know in party:
            trueParty += 1
            break

print(M - trueParty)

 

 

 

3. 최적화 1+2

import sys
input = sys.stdin.readline

# 사람의 수, 파티의 수
N, M = map(int, input().split())
# 진실을 아는 사람의 수, 번호가 주어짐
knowList = set(map(int, input().split()[1:]))
# 각 파티에 오는 사람의 수, 번호
partyList = [set(map(int, input().split()[1:])) for _ in range(M)]

for _ in range(M):
    knowListLength = len(knowList)

    for party in partyList:
        # 파티 참석자 중에 진실을 알고 있는 사람이 있다면
        if knowList & party:
            knowList = knowList.union(party)

    # 모든 파티를 탐색했음에도 더 이상 "진실파티"가 갱신이 되지 않는 경우 탐색을 종료한다.
    if knowListLength == len(knowList):
        break

trueParty = 0
for party in partyList:
    for know in knowList:
        if know in party:
            trueParty += 1
            break

print(M - trueParty)

 

 

 

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

저작자표시 (새창열림)

'Algorithm > Data Structure' 카테고리의 다른 글

[백준] 5052번 전화번호 목록 _ Java, Python  (0) 2024.03.02
[백준] 14426번 접두사 찾기 _ JAVA  (0) 2024.02.21
[백준] 14725번 개미굴 _ Python  (0) 2024.02.09
'Algorithms/Data Structure' 카테고리의 다른 글
  • [백준] 5052번 전화번호 목록 _ Java, Python
  • [백준] 14426번 접두사 찾기 _ JAVA
  • [백준] 14725번 개미굴 _ Python
wch_t
wch_t
  • wch_t
    끄적끄적(TIL)
    wch_t
  • 글쓰기 관리
  • 전체
    오늘
    어제
    • 분류 전체보기 (171)
      • Architecture (0)
      • Algorithm (67)
        • Math (5)
        • Simulation (1)
        • Data Structure (4)
        • DP (7)
        • Brute Fource (10)
        • Binary Search (6)
        • Greedy (2)
        • Graph (11)
        • Mst (1)
        • Shortest path (10)
        • Two Pointer (1)
        • Tsp (3)
        • Union Find (2)
        • Mitm (1)
      • CS (2)
        • 데이터베이스 (5)
        • 네트워크 (5)
      • DB (6)
      • DevOps (17)
        • AWS (9)
        • Docker (1)
        • CI-CD (5)
      • Error (1)
      • Project (0)
        • kotrip (0)
      • Spring (59)
        • 끄적끄적 (5)
        • 기본 (9)
        • MVC 1 (7)
        • MVC 2 (11)
        • ORM (8)
        • JPA 1 (7)
        • JPA 2 (5)
        • Spring Data Jpa (7)
      • Test (2)
      • TIL (6)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    Sxssf
    spring-cloud-starter-bootstrap
    apache poi
    docker
    Jenkins
    aws secrets manager
    view algorithm
    spring-cloud-starter-aws-secrets-manager-config
    response_mode
    백준 3015 파이썬
    애플
    Merge
    백준 17299 파이썬
    TempTable
    form_post
    scope
    docker: not found
    백준 17289 파이썬
  • 최근 댓글

  • hELLO· Designed By정상우.v4.10.3
wch_t
[백준] 1043번 거짓말 _ Python
상단으로

티스토리툴바