인프런 커뮤니티 질문&답변
작성한 질문수
구현 측면 질문이 있습니다.
작성
·
238
1
안녕하세요 선생님.
저의 경우에는 39번 문제의 두 배열을 합치는 매카니즘을 이용하여 해결하였습니다.
0. 사용자로 부터 두 배열을 입력
1. 입력받은 두 배열을 각각 정렬 알고리즘을 사용하여 오름차순으로 각각 정렬
2. 오름차순으로 정렬된 두 배열을 합친다
3. 이후 합쳐진 결과가 저장된 배열에서 중복된값만을 출력한다
저의 경우는 위의 논리를 기반으로 구현하였습니다.(사실상 39번 구현 코드와 큰 차이가 없습니다)
제 생각으로는 이렇게 구현하여도, 시간복잡도 측면을 생각해 본다면 선생님이 설명해 주신 투포인터 알고리즘으로 구현하든, 제 방식으로 구현하든 , 시간복잡도 측면은 동일하다고 생각되는데요, 제가 맞게 생각한건지 궁금합니다.
-> 어차피 논리가 다른 부분은 위의 과정에서 두 배열을 합치냐 아니면 vs 바로 비교하냐 인데 , 두배열을 합치든 바로 비교하든 결국 두 방법에서 사용되는 loop은 어차피 배열 하나만을 scan하는 O(n)의 시간복잡도를 갖는다고 생각합니다.
퀴즈
57%나 틀려요. 한번 도전해보세요!
선택 정렬(Selection Sort) 알고리즘은 각 단계에서 어떤 작업을 수행하여 배열을 정렬하나요?
인접한 두 요소를 비교하여 필요시 교환합니다.
정렬되지 않은 부분에서 가장 작은(또는 큰) 값을 찾아 정렬된 부분의 올바른 위치로 옮깁니다.
현재 요소를 이미 정렬된 부분 배열의 적절한 위치에 삽입합니다.
배열을 분할하고 각 부분을 재귀적으로 정렬한 후 병합합니다.
