구현 측면 질문이 있습니다.

Question

안녕하세요 선생님. 저의 경우에는 39번 문제의 두 배열을 합치는 매카니즘을 이용하여 해결하였습니다. 0. 사용자로 부터 두 배열을 입력 1. 입력받은 두 배열을 각각 정렬 알고리즘을 사용하여 오름차순으로 각각 정렬 2. 오름차순으로 정렬된 두 배열을 합친다 3. 이후 합쳐진 결과가 저장된 배열에서 중복된값만을 출력한다 저의 경우는 위의 논리를 기반으로 구현하였습니다.(사실상 39번 구현 코드와 큰 차이가 없습니다) 제 생각으로는 이렇게 구현하여도, 시간복잡도 측면을 생각해 본다면 선생님이 설명해 주신 투포인터 알고리즘으로 구현하든, 제 방식으로 구현하든 , 시간복잡도 측면은 동일하다고 생각되는데요, 제가 맞게 생각한건지 궁금합니다. -> 어차피 논리가 다른 부분은 위의 과정에서 두 배열을 합치냐 아니면 vs 바로 비교하냐 인데 , 두배열을 합치든 바로 비교하든 결국 두 방법에서 사용되는 loop은 어차피 배열 하나만을 scan하는 O(n)의 시간복잡도를 갖는다고 생각합니다.

김태원 · Answer

안녕하세요^^ 네. 맞습니다. 거의 동일한 복잡도입니다.