Search
Duplicate
🎍

배열의 가장 첫 번째 중복 요소 알아내기

1.
이중 배열 사용 (공간복잡도 O(1)O(1), 시간복잡도 O(N2)O(N^2))
: i, j 인덱스 선언 후, i는 0부터 len(arr)까지 j는 i부터 len(arr)까지 돌면서 동일 요소 검색
2.
Hash Map 사용(공간복잡도 O(N)O(N), 시간복잡도 O(N)O(N))
: arr의 길이와 같은 Map을 생성, 각 값들은 0으로 초기화되어있는 상태, arr의 길이만큼 반복문을 수행하며 해당 값을 발견하면 1로 변경, 만약 1인 경우엔 중복값이므로 해당 값 반환
3.
퀵 정렬 사용 (공간복잡도 O(logN)O(logN), 시간복잡도 O(NlogN)O(NlogN))
: 퀵 정렬 사용(공간복잡도 O(logN)O(logN), 시간복잡도 O(NlogN)O(NlogN))하여 정렬 후, i는 0부터 len(arr)까지 j는 i + 1로 반복문을 순회하며 arr[i], arr[j]가 같은 값인 경우 반환 → O(N)O(N)
4.
병합 정렬 사용 (공간복잡도 O(1)O(1), 시간복잡도 O(NlogN)O(NlogN))
: 병합 정렬 사용(공간복잡도 O(1)O(1), 시간복잡도 O(NlogN)O(NlogN))하여 정렬 후, i는 0부터 len(arr)까지 j는 i + 1로 반복문을 순회하며 arr[i], arr[j]가 같은 값인 경우 반환 → O(N)O(N)
5.
내가 모르는 방법..
: 3, 4번의 경우, 해당 배열이 변경된다는 이슈가 발생, 이런 변경을 허용하지 않고 공간복잡도 O(1)O(1), 시간복잡도 O(NlogN)O(NlogN)의 알고리즘을 구현하라
: 이진 탐색..
Made with