글 읽기 - 1764 듣보잡) 딕셔너리 안쓰고 시간 내에 풀 수 있는 방법이 있나요?

diluny 2년 전 0

set은 너무 라이브러리 날먹 풀이인 거 같아서, 구현을 할 줄은 알아야겠다고 생각해서 딕셔너리로도 시도해보고, 배열로도 시도 해봤습니다. 그런데 아래 소스코드처럼 풀면 (배열 이용) in 이용해서 리스트에 있는지 탐색하는 시간 때문에 시간 초과가 뜨더라구요. (시간 복잡도 O(n^2)) 딕셔너리 말고 배열 써서는 풀 수 있는 방법이 없나요? 아님 탐색을 좀 더 빠르게 해주면 되나요?

import sys
s1 = []
s2 = []
n, m = map(int, input().split())
for i in range(n):
    s1.append(sys.stdin.readline().rstrip())
for i in range(m):
    name = sys.stdin.readline().rstrip()
    if name in s1:
        s2.append(name)
s2.sort()
print(len(s2))
for x in s2:
    print(x)

ehdrmsl2001 2년 전 1

탐색할 때 이분 탐색 이용해보세요

diluny 2년 전 0

넹! 감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1764 듣보잡) 딕셔너리 안쓰고 시간 내에 풀 수 있는 방법이 있나요?

diluny 2년 전 0

ehdrmsl2001 2년 전 1

diluny 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말