[BOJ] [Python] 1764 : 듣보잡

듣도 보도 못한 사람의 명단을 구하는 문제이다.

 

무식하게 문제를 풀면 시간 복잡도가 O(N x M)이 된다.

그리고 500,000 x 500,000 = 250,000,000,000으로 시간초과가 난다.

 

듣도 못한 사람의 명단을 A, 보도 못한 사람의 명단을 B  라고 했을 때

하나만 정렬된 명단이라면, 이진탐색이 가능해진다.

 

 

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

li_n = []
li_m = []

for _ in range(n):
    li_n.append(input())

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

li_m.sort()


def BSearch(target):
    low = 0
    high = len(li_m) - 1

    while low <= high:
        mid = (low + high) // 2

        if li_m[mid] == target:
            result.append(target)
            return

        elif li_m[mid] < target:
            low = mid + 1

        else:
            high = mid - 1
    return


result = []

for string in li_n:
    BSearch(string)

print(len(result))
result.sort()

for string in result:
    print(string)

 

 

(aaa < abc 는 Fasle이다.)

 

python 내장함수인 sort는 시간 복잡도가 O(N log N)이다.

M번 반복하는 이진탐색의 시간 복잡도는 O(M log N)이다.

 

 

 

 

다른 사람 풀이를 보니까, 교집합 연산자를 사용했더라.

 

list(set(n_li) & set(m_li))

 

교집합 연산자를 사용하면, 리스트의 순서를 보장하지 않아도 된다.

 

시간 복잡도는 O(N + M)이다.

 

 

(왜 시간 복잡도가 O(N + M)인지는 모르겠다. 내장함수 코드를 찾고 싶은데 못 찾았기 때문...)