본문 바로가기
백준 문제풀이

[백준] 1764번 듣보잡 - Python

by arctis7p 2024. 12. 10.

문제 링크: https://www.acmicpc.net/problem/1764

 

이 문제는 다음과 같이 요약할 수 있습니다.

 

문제 개요

  • 듣도 못한 사람의 명단과 보도 못한 사람의 명단이 주어짐
  • 듣도 보도 못한 사람(듣보잡)의 명단을 찾아 출력하는 프로그램 작성

입력

  • 첫째 줄: 듣도 보도 못한 사람의 수 N, 보도 못한 사람의 수 M
  • 다음 N개 줄: 듣도 못한 사람의 이름
  • 그다음 N개 줄: 보도 못한 사람의 이름
  • 각 명단에 중복되는 이름은 없음

출력

  • 듣보잡의 수
  • 듣보잡의 명단을 사전순으로 출력

핵심 요구사항

  • 두 명단에서 공통으로 등장하는 이름을 찾아야 함
  • 결과를 사전순으로 정렬해야 함
  • 대량의 데이터를 처리해야 함(N, M이 최대 500,000)

 


이제 코드를 한 번 살펴보겠습니다. 아래는 전체 코드입니다.

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
N_data = set(input().strip() for _ in range(N))
M_data = [input().strip() for _ in range(M)]

stack = 0
result = []
for people in M_data:
    if people in N_data:
        stack += 1
        result.append(people)

print(stack)
print('\n'.join(sorted(result)))
  1. 입력 최적화
    import sys
    input = sys.stdin.readline
    • 대량의 데이터를 처리해야 하므로 sys.stdin.readline을 사용하여 입력 속도를 향상시킵니다.
  2. 데이터 입력 및 저장
    N, M = map(int, input().split())
    N_data = set(input().strip() for _ in range(N))
    M_data = [input().strip() for _ in range(M)]
    • N과 M을 입력받아 각각 듣도 못한 사람과 보도 못한 사람의 수를 저장합니다.(구조분해할당)
    • N_data는 set으로 저장하여 검색 속도를 O(1)로 최적화합니다.
    • M_data는 리스트로 저장하여 순차적 접근을 가능하게 합니다. O(N).
    • 재정의된 input() 함수는 개행문자를 포함하기 때문에 strip()을 사용하여 개행문자를 제거합니다.
  3. 듣보잡 찾기
    stack = 0
    result = []
    for people in M_data:
        if people in N_data:
            stack += 1
            result.append(people)
    • M_data의 각 이름을 N_data에서 검색합니다. 리스트의 검색 속도는 O(M)입니다.
    • 여기서 N_data는 set이므로 in 검색에서의 속도는 O(1)입니다.
    • 중복된 이름을 발견하면 stack을 증가시키고 result에 추가합니다.
  4. 결과 정렬 및 출력
    result.sort()
    
    print(stack)
    print(*result, sep="\n")
    • result 리스트를 사전 순으로 정렬합니다.
      • 이 연산의 시간 복잡도는 O(M log M)입니다.(result의 길이 M)
    • stack을 출력하여 듣보잡의 수를 나타냅니다.
    • *result로 리스트를 언패킹 하고, sep="\n"으로 각 이름을 새 줄에 출력합니다.

전체 시간 복잡도는 O(M log M)입니다.

 

 

# 이 글의 내용 중 일부는 Perplexity AI의 도움을 받아 정보를 수집하고 정리하였으며, 추가적인 연구와 개인적인 견해를 더하였습니다.