[BOJ] 백준 1764 듣보잡 / 이분탐색

이미지를 클릭하면 문제 사이트로 이동합니다.

 

 

💭 문제 이해

 

제목이....ㅋ

암튼 전형적인 방법으로 풀면 이분탐색이지만,

파이썬의 장점을 잘 살리면 이분탐색보다 실행속도도 더 빠르고 간단하게 풀어낼 수 있다.

 

풀이 방법은 다음과 같다.

1. 이분탐색

2. Set 자료구조와 in 연산자

3. Set의 교집합을 구할 수 있는 & 연산자

4. Set과 intersection 메소드를 이용한 교집합 연산

 

실행속도는 4 > 3 >= 2 > 1 순으로 빠르다.

 

 

 

구현 언어: Python

 

 

1. 이분탐색

import sys

r = sys.stdin.readline

def binary_search(d_list: list, b_list: list) -> list:
    result = []
    d_list.sort()
    for b in b_list:
        left = 0
        right = len(d_list) - 1
        while left <= right:
            mid = (left + right) // 2
            if d_list[mid] < b:
                left = mid + 1
            elif d_list[mid] > b:
                right = mid - 1
            else:
                result.append(b)  # 듣도 보도 못한 명단 찾음
                break  # 여기서 꼭 종료를 해주어야 한다!
    return sorted(result)

d_num, b_num = map(int, r().split())
d_list = list(r().rstrip() for _ in range(d_num))  # 듣도 못한 명단
b_list = list(r().rstrip() for _ in range(b_num))  # 보도 못한 명단
answer = binary_search(d_list, b_list)  # 사전순으로 정렬된 듣도 보도 못한 명단
print(len(answer))
for name in answer:
    print(name)

 

 

2. Set 자료구조와 in 연산자

import sys

r = sys.stdin.readline

d_num, b_num = map(int, r().split())
d_list = set(r().rstrip() for _ in range(d_num))  # 듣도 못한 명단
b_list = list(r().rstrip() for _ in range(b_num))  # 보도 못한 명단
answer = sorted([name for name in b_list if name in d_list])
print(len(answer))
for name in answer:
    print(name)

Set은 Hash function으로 구현이 되어있어서 Dict를 사용할 때처럼 in 연산자를 O(1)의 시간으로 사용할 수 있어 매우 빠르다!

 

 

3. Set의 교집합을 구할 수 있는 & 연산자

import sys

r = sys.stdin.readline

d_num, b_num = map(int, r().split())
d_list = set(r().rstrip() for _ in range(d_num))  # 듣도 못한 명단
b_list = set(r().rstrip() for _ in range(b_num))  # 보도 못한 명단
answer = sorted(d_list & b_list)
print(len(answer))
for name in answer:
    print(name)

 

 

4. Set과 intersection 메소드를 이용한 교집합 연산

import sys

r = sys.stdin.readline

d_num, b_num = map(int, r().split())
d_list = set(r().rstrip() for _ in range(d_num))  # 듣도 못한 명단
b_list = set(r().rstrip() for _ in range(b_num))  # 보도 못한 명단
answer = sorted(d_list.intersection(b_list))  # 내장 메소드가 더 빠름!!
print(len(answer))
for name in answer:
    print(name)