[#1764] 듣보잡

문제

#1764 듣보잡
Silver4
적용 알고리즘: 이분 탐색 알고리즘

---

풀이 방법

• 수의 범위 때문에 Brute Force 알고리즘으로 하면 시간초과가 난다. (최대 500,000 * 500,000)
• 이분 탐색 알고리즘을 사용한다.
• String 간의 대소 관계가 존재한다.(알파벳 순서)

코드 흐름

1. 사용자의 입력을 받고, 듣도 못한 사람과 보도 못한 사람을 다른 배열에 저장하고 이를 각각 정렬한다.
2. 보도 못한 사람(bo)에 대해서 듣도 못한 사람(dut)의 한명한명마다 이분탐색을 실행한다. 만일 이름이 같다면 듣도보도못한 사람이므로 이를 정답 배열에 저장한다.
3. 정답 배열은 이미 정렬이 되어 있다. 이 배열의 길이와(사람 명 수), 사람의 이름을 출력한다.

코드

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

dut = [input() for _ in range(n)]
bo = [input() for _ in range(m)]
dut.sort()
bo.sort()

answer = []

# bo를 배경으로 깔음
for name in dut:
    low = 0
    high = len(bo) - 1
    while (low <= high):
        mid = (low + high) // 2

        if (name == bo[mid]):
            answer.append(name)
            break
        if (name < bo[mid]):
            high = mid - 1
        if (name > bo[mid]):
            low = mid + 1

print(len(answer))
for i in answer:
    print(i)

체감 난이도: 3.8/5
사실 String 관련 문제를 풀었어야 했는데 어쩌다 이분탐색 문제를 풀어버렸다.Brute Force 로 풀면 테스트 케이스에 대한 답은 나오지만 채점을 하면 시간 초과가 나온다. 그래도 예전에 이분탐색을 좀 풀어봤어서 그런지 이분탐색 알고리즘 구현은 좀 익숙해진 것 같다.