투 포인터라고 하는 기법을 사용하신 것입니다.
find 함수는 말씀하신 것처럼 선형이 맞습니다. 두 배열에 대한 포인터가 각각 O(N), O(M)번만 증가하고 그 과정에서 상수 시간 이외의 연산을 하지 않기 때문입니다.
다만 알고리즘 전체의 시간 복잡도는 이분 탐색을 사용하는 것과 같이 로그가 붙는데, 이는 sort 함수가 그만큼의 시간 복잡도를 가지기 때문입니다.
수행 시간이 느린 건 그보다는 입출력이 느린 탓이 큽니다. https://www.acmicpc.net/proble... 를 풀어보세요.

gbs17_shj 7달 전
안녕하세요
이진탐색은 시간복잡도에 벗어날 것 같다고 생각해서 사용하지 않았는데, 당연히 nlogn으로 통과되는 것이었습니다.
그런데 제가 작성한 알고리즘은 시간복잡도가 어떤 것인지 잘 모르겠습니다.
소요 시간만 보면 빠른 것 같지는 않고, 알고리즘을 검토해보면 선형이라고 생각하는데 확실하지 않습니다.
알려주시면 감사하겠습니다!
+ 혹시 이렇게 튜플을 사용하지 않고도 같은 알고리즘을 사용할 수 있을까요?? 코드가 지저분해진 것 같습니다..;;