[Python] 백준 1764번 : 듣보잡 <Silver 4>

⚠️ 내맘대로 작성한 코드이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️

 

https://www.acmicpc.net/problem/1764

1764번: 듣보잡

Code

---

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

NList = set()
for i in range(N):
    NList.add(input().strip())

MList = set()
for i in range(M):
    MList.add(input().strip())

result = sorted(NList & MList)

print(len(result))
for i in result:
    print(i)

---

Code 필수 요소

1. 시간 초과가 나지 않는 방법

2. set 사용법

 

이것만 생각해내면 절반은 끝났다.

 

// 시간초과가 나지 않는 방법

난 여기서 시간이 제일 많이 걸렸다.

처음 사용한 방법은 리스트를 만들어서 N의 값을 받고, M의 값을 받음과 동시에 N리스트와 비교하여 결과값 리스트에 넣어주는 방식이었다.  하지만 시간초과가 발생했다.

그래서 N리스트를 받은 후 M값을 받기 전에 N리스트를 정렬 시키고 M리스트를 받으며 N리스트와 비교하는데 값이 더 커질경우 break시키는 방법으로 시간을 줄여보려 했다.  그래도 시간 초과다. 그게 아래와 같은 코드다.

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
list = []
result = []

for i in range(N):
    list.append(input().strip())
list.sort()

for i in range(M):
    name = input().strip()
    for j in range(N):
        if list[j] > name:
            break
        if list[j] == name:
            result.append(name)

result.sort()

print(len(result))
for i in result:
    print(i)

이렇게 해서 안된다면 다른 방법이 있을거라고 생각하고 구글링 하니까 파이썬에는 set이라는 집합 자료형이 있더라. 그래서 그걸 활용해서 다시 만들었더니 시간 초과가 안났다.

 

// set사용법

set을 만들고 거기에 N번 값을 입력해 넣었다. 그리고 set을 하나 더 만들어서 M번 값을 입력해 넣었다.

두개의 set을 비교해서 교집합을 찾아내 result에 정렬하여 넣었다.

 

 솔직히 말하면 원리는 모르겠다. set두개 만들고 교집합 찾는방법이 더 빠른가보다.

 

이번에 코드에는 input()뒤에 .strip()이 있는데 이거 없으면 \n까지 입력이 된다. 그래서 넣었다. 

 

 

내 생각에는 내가 처음 생각한 코드도 꽤나 괜찮았는데 이게 막히네 쩝... 아쉽다. list를 하나씩 비교하는게 문제였나? sort를 여러번 하는게 문제였나? 모르겠다. set으로 문제는 풀었는데 아직 set사용법을 잘 모른다. 공부할거 하나 추가요...

 

-꿑-