1. Problem 📃
📚 출처 - 1764 - 듣보잡
문제 설명
김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.
듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.
출력
듣보잡의 수와 그 명단을 사전순으로 출력한다.
입출력 예
| 예제 입력 | 예제 출력 |
|---|---|
| 3 4 ohhenrie charlie baesangwook obama baesangwook ohhenrie clinton | 2 baesangwook ohhenrie |
2. Logic 👨🏫
Logic 1
첫 번째 로직은 리스트로 입력을 모두 받은 후in으로 둘 다 있는지 check 한 뒤 있으면 정렬해 반환하는 방식으로 해결하였습니다. 하지만 이 방법은 시간 초과로 통과하지 못했습니다.
그래서 어떤게 부족했나 찾아봤는데list대신set을 이용해 해결하는 방법이 있었습니다.
Logic 2
set을 이용해 해결한 code 입니다. Logic은 위와 동일합니다. 다만 set에서 약간 특이한 부분이 있었는데 그 부분은 아래서 설명하겠습니다.
3. Code 💻
1. 첫 번째로 푼 코드 😥 (시간 초과)
N, M = map(int, input().split())
d_ListenList = [] # 듣도 못한 사람의 수
d_SeeList = [] # 보도 못한 사람의 수
result = []
for i in range(N):
d_ListenList.append(input())
for i in range(M):
d_SeeList.append(input())
for i in d_ListenList:
if i in d_SeeList:
result.append(i)
print(len(result))
result.sort()
for i in result:
print(i)2. 두 번째로 푼 코드 😁 (통과)
N, M = map(int, input().split())
d_Listen = set() # 듣도 못한 사람의 수
d_See = set() # 보도 못한 사람의 수
for i in range(N):
d_Listen.add(input())
for i in range(M):
d_See.add(input())
result = sorted(list(d_Listen & d_See))
print(len(result))
for i in result:
print(i)4. Feedback 📚
1. set()
set의 기능은 아주 다양하지만 여기서는 이번에 사용된 부분에 관련해서만 포스팅 할 생각이다. 혹시 더 많은 기능을 보고싶다면 아래의 참고 자료를 확인해보자.
먼저 파이썬에서 set은 해시 테이블(hash table)로 구현되어 있어 평균 시간 복잡도가 O(1)이 된다. 위의 list로 했을때는 시간 초과가 발생했지만 set으로 구현했을 때 통과한 걸 보니 시간 복잡도가 다음과 같아서 차이가 있었던 것 같다.
리스트에서의 x in s 연산의 평균 시간 복잡도 : O(n)
세트에서의 x in s 연산의 평균 시간 복잡도 : O(1)
1. add()
list에서 원소를 추가하려면 append를 사용하면 되지만, set에서는 add를 사용하면 된다.
>>> s1 = set([1, 2, 3])
>>> s1.add(4)
>>> s1
{1, 2, 3, 4}2. 교집합, 합집합, 차집합
list에서는 x in s로 확인해서 중복되는 값을 처리해줬다면 set에서는 기능이 바로 있었다.
교집합
먼저 교집합부터 살펴보면
# 교집합
>>> s1 = set([1, 2, 3, 4, 5, 6])
>>> s2 = set([4, 5, 6, 7, 8, 9])
# 방법 1
>>> s1 & s2
{4, 5, 6}
# 방법 2
>>> s1.intersection(s2)
{4, 5, 6}합집합
# 합집합
# 방법 1
>>> s1 | s2
{1, 2, 3, 4, 5, 6, 7, 8, 9}
# 방법 2
>>> s1.union(s2)
{1, 2, 3, 4, 5, 6, 7, 8, 9}차집합
# 차집합
# 방법 1
>>> s1 - s2
{1, 2, 3}
>>> s2 - s1
{8, 9, 7}
# 방법 2
>>> s1.difference(s2)
{1, 2, 3}
>>> s2.difference(s1)
{8, 9, 7}2. {}와 set()의 차이
{} 자체만으로는 dict을 선언하는 것입니다.
set() 선언을 하게 되면 set으로 생성 가능합니다.
s = set([1, 2, 3])
print(type(s)) # set
s = {}
print(type(s)) # dictset과 Dictionary의 차이
| set | Dictionary |
|---|---|
| key 값만 가지고 있음 | key, value 값을 가지고 있음 |
| mutable list형임 | key(immutable), value(mutable) 형식이다. |
참고 자료 📩
Python set 공식문서
set과 Dictionary의 차이
