듣보잡 - 1764

듣보잡

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	256 MB	107225	46136	35916	41.273%

문제

김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.

듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.

출력

듣보잡의 수와 그 명단을 사전순으로 출력한다.

예제 입력 1

3 4
ohhenrie
charlie
baesangwook
obama
baesangwook
ohhenrie
clinton

예제 출력 1

2
baesangwook
ohhenrie

---

► Idea

1. 듣도 못 한 사람, 보도 못 한 사람 명단
2. 두 개의 명단에 모두 있는 사람 명단
3. 그 사람들의 수와, 오름차 순 정렬하여 출력
4. 파이썬 자료구조의 활용
5. set 활용

---

► Code

import collections

res = []
n, m = map(int, input().split(" "))

li1 = list()
li2 = list()

for i in range(0, n + m):
  s = input()
  if i < n:
    li1.append(s)
  else:
    li2.append(s)
set1 = set(li1)
set2 = set(li2)
intersected_set = set1.intersection(set2)
intersected_list = list(intersected_set)

intersected_list.sort()
print(len(intersected_list))
for i in range(len(intersected_list)):
  print(intersected_list[i])

---

► 시간 소요한 부분

시간초과 Java, Python

• 시간 복잡도 O(n^2)

1. 인풋 들어올 때마다 리스트 순회: 시간 복잡도 O(n)
2. for loop 내에서 실행되므로 O(n)

입력 크기에 따라 실행 시간이 제곱 증가하여 당연히 시간초과다.

def find_Str(s, li):
  cnt = 0
  for i in range(len(li)):  # This will work whenever inputs are added into the array.
    if s == li[i]:  # Time Complexity: O(n)
      cnt += 1
  return cnt


li = []
for i in range(0, n + m):

  s = input()
  if i < n:
    li.append(s)
  if i >= m:
    if any(str in s for str in li) == True:
      res.append(s)
    else:
      continue

print(len(res))
res.sort()
for i in range(len(li) - 1):
  print(res[i])

시간 초과 해결

파이썬 collections 라이브러리와 set 자료구조를 활용한다.

set: 중복되지 않는 항목 집합 저장

set1 = set(li1)
set2 = set(li2)
intersected_set = set1.intersection(set2)  # Store it into a new set named intersected_set
intersected_list = list(intersected_set)

당연히 값이 들어올 때마다 for loop를 순회하면 시간초과고, 애초에 문제에서도 그걸 노리고 낸 듯하다. 적절한 자료구조와 라이브러리 활용하자..