[백준/알고리즘/python/java] 1764번 - 듣보잡

이미지를 누르면 문제링크를 보실 수 있습니다.

이미지를 누르면 문제링크를 보실 수 있습니다.

정답 비율이 높지 않아서, 뭔가 시간초과와 관련된 문제이겠거니 싶었다.

역시나 처음 풀었던 코드는 시간초과에 걸렸다.

아래는 처음 시간초과에 걸렸던 코드이다.

import sys
import collections
input = sys.stdin.readline


a, b = map(int, input().split())
answer = []
no_heard = [input().strip() for i in range(a)]
no_seen = [input().strip() for i in range(b)]

if a < b:
    for word in no_heard:
        if(word in no_seen):
            answer.append(word)

else:
    for word in no_seen:
        if(word in no_heard):
            answer.append(word)

answer.sort()
print(len(answer))
for word in answer:
    print(word)

strip()이라는 함수로 입력받은 문장에서 개행문자를 없애준채로 각 리스트에 저장하였고,

a와 b 둘 중에 더 작은 숫자가 무엇인지에 따라 기준 리스트를 정한다음에 순회하면서 겹치는 걸 answer리스트에 넣어서 찾았다. 

로직은 정말 단순한데, 내가봐도 시간복잡도에 문제가 있는 코드였다.

어떻게 빨리 풀 수 있냐가 관건인데, 쉽게 생각해 set 을 쓰면 됐다.

set은 말그대로 집합이다. 지금 우리가 필요한 것은 교집합인데, 파이썬에서는 집합의 여러 기능 등을 제공한다.

set.intersection(a, b) 은 a와 b의 교집합을 구하는 것으로 a & b 로도 표현가능 하다.

이외에도, 차집합은 difference(-), 합집합은 union( | ) 등을 씀으로써 찾아낼 수 있다.

 

아래는 수정한 코드이다.

import sys
import collections
input = sys.stdin.readline


a, b = map(int, input().split())

no_heard = [input().strip() for i in range(a)]
no_seen = [input().strip() for i in range(b)]

answer = list(set(no_heard) & set(no_seen))

answer.sort()
print(len(answer))
for word in answer:
    print(word)

set으로 시간초과 문제를 해결할 수 있었다.

여기서 and 는 쓰면 안된다.

추후에 기본적인 and와 & or 과 |

=과 is 등의 차이를 정리해야겠다.

 

(추후 정리 링크)

https://letzgorats.tistory.com/entry/Python-is%EC%99%80-and%EC%99%80-or%EA%B3%BC?category=916568