목록정렬 (1)

Trey

백준 1764번: 듣보잡 - 파이썬

백준 1764번: 듣보잡 (www.acmicpc.net/problem/1764) 💡접근 제한 시간 : 2초 듣도 못한 사람 리스트, 보도 못한 사람 리스트에서 중복 원소를 찾아야하는 문제이다. 두개의 리스트를 만들어 이중 for loop으로 모든 원소를 비교할 경우, 최악의 경우 50만x50만 = 2500억번의 연산을 해야하므로 시간초과가 날 수 있다. 따라서, 탐색하는 시간이 O(1)걸리는 python dictionary를 사용해서 풀어보면 어떨까? 먼저, 듣도 보도 못한 종류의 관계없이, 이름을 key값으로 가져가고, key가 처음 생기는 경우라면 1을 넣어준다. → 삽입에 총 O(n) 시간복잡도가 소요됨 key값이 앞에서 만들어져있는 상태에서 또 같은 key값이 입력값으로 들어온다면, 해당 key값..
알고리즘 문제 풀이 (Class 3) 2021. 3. 21. 17:33
이전 Prev 1 Next 다음