2018. 1. 5. 23:40, 알고리즘/BOJ
https://www.acmicpc.net/problem/1764
만약 두 리스트를 이중 for문을 돌면서 일치하는 원소가 있는지 확인한다면 O(NM)이지만 두 리스트를 sorting한 이후, 비교를 한다면 traversal을 할 때 무조건 하나의 원소는 더이상 보지 않아도 됨이 보장되기 때문에 시간복잡도를 O(NlgN+MlgM)으로 떨굴 수 있습니다.
'알고리즘 > BOJ' 카테고리의 다른 글
| [BOJ] 1915번: 가장 큰 정사각형 (0) | 2018.01.05 |
|---|---|
| [BOJ] 11504번: 가장 긴 바이토닉 부분 수열 (0) | 2018.01.05 |
| [BOJ] 1983번: 숫자 박스 (0) | 2018.01.05 |
| [BOJ] 14488번: 준오는 급식충이야!! (0) | 2018.01.05 |
| [BOJ] 10974번: 모든 순열 (0) | 2018.01.05 |
| [BOJ] 1504번: 특정한 최단 경로 (0) | 2018.01.05 |
Comments