[백준] 1764번: 듣보잡(Python)

1. 문제 링크

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

1764번: 듣보잡

2. 풀이

1) 문제 풀이

• 각 50만개씩인 명단 2개
• in으로 판별(시간 초과, n^2 = 2500억개) -> 이진탐색(풀림, 시간 복잡도 50만 * logN = 50만 * 11 정도) -> set활용(풀림, 제일 간단, O(len(s) + len(t)) = 2 * 50만)

 두 집합의 교집합, 합집합, 차집합은 2 * O(n)이 2000만을 넘지 않는다면 set 쓰자.

 

2) 풀이 코드

- 이진 탐색 방법

import sys
input = sys.stdin.readline

n, m = map(int, input().split())

see = []
listen = []
for _ in range(n):
    see.append(input())

for _ in range(m):
    listen.append(input())

see.sort()
listen.sort()
result = []

def binary_search(array, item, length):
    start = 0
    end = length - 1

    while start <= end:
        mid = (start + end) // 2
        if array[mid] == item:
            return True
        elif array[mid] < item:
            start = mid + 1
        else:
            end = mid - 1

    return False

if n < m:
    # listen 기준 탐색
    for i in range(n):
        if binary_search(listen, see[i], m):
            result.append(see[i])
else:
    for i in range(m):
        if binary_search(see, listen[i], n):
            result.append(listen[i])

print(len(result))
print('\n'.join(result))

 

- set 풀이

import sys
input = sys.stdin.readline

n, m = map(int, input().split())

s1 = set()
s2 = set()

for _ in range(n):
    s1.add(input())
for _ in range(m):
    s2.add(input())

result = list(sorted(s1 & s2))

print(len(result))
print(''.join(result))

 

3. 결과