문제 링크: 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)))
- 입력 최적화
import sys input = sys.stdin.readline
- 대량의 데이터를 처리해야 하므로 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)]
- N과 M을 입력받아 각각 듣도 못한 사람과 보도 못한 사람의 수를 저장합니다.(구조분해할당)
- N_data는 set으로 저장하여 검색 속도를 O(1)로 최적화합니다.
- M_data는 리스트로 저장하여 순차적 접근을 가능하게 합니다. O(N).
- 재정의된 input() 함수는 개행문자를 포함하기 때문에 strip()을 사용하여 개행문자를 제거합니다.
- 듣보잡 찾기
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에 추가합니다.
- 결과 정렬 및 출력
result.sort() print(stack) print(*result, sep="\n")
- result 리스트를 사전 순으로 정렬합니다.
- 이 연산의 시간 복잡도는 O(M log M)입니다.(result의 길이 M)
- stack을 출력하여 듣보잡의 수를 나타냅니다.
- *result로 리스트를 언패킹 하고, sep="\n"으로 각 이름을 새 줄에 출력합니다.
- result 리스트를 사전 순으로 정렬합니다.
전체 시간 복잡도는 O(M log M)입니다.
# 이 글의 내용 중 일부는 Perplexity AI의 도움을 받아 정보를 수집하고 정리하였으며, 추가적인 연구와 개인적인 견해를 더하였습니다.
'백준 문제풀이' 카테고리의 다른 글
[백준] 2108번 통계학 - Python(1편) (1) | 2024.12.11 |
---|---|
[백준] 10815번 숫자 카드 - Python(1편) (0) | 2024.12.10 |
[백준] 10816번 숫자 카드 2 - Python (3) | 2024.12.10 |
[백준] 11651번 좌표 정렬하기2 - Python (0) | 2024.12.10 |
[백준] 1931번 회의실 배정 - Python (0) | 2024.12.10 |