[5. 배열] 5.5 정렬된 배열에서 중복 제거하기

[해당 문제는 266가지 문제로 정복하는 코딩 인터뷰]
책의 내용의 문제와 풀이를 베이스로 공부하는 내용이다. 

문제를 풀기전에 단순하게 문제를 푸는것이 목적이 아닌
시간복잡도와 공간복잡도의 관계를 계산하며,
자료구조의 이해도와 실력을 향상하는데 목적이 있다.

---

[5. 배열] 단원의 기본 셋팅은 다음과 같다.

---

Q 5.5 정렬된 배열에서 중복 제거하기

정렬된 배열이 입력으로 주어졌을 때 중복으로 원소를 모두 제거한 뒤, 비어있는 공간이 생기지 않도록 유효한 원소들을 모두 왼쪽으로 시프트하는 프로그램을 작성하라.

---

이 문제는 시프팅이 시간 복잡도의 주요 원인이다. 시간 복잡도를 줄이기 위해서 시프팅의 횟수를 줄이는 방향을 생각하자.
배열이 이미 정렬되어 있으므로 단순히 원소 한번만 옮겨서 정리해보면 다음과 같다.

시간복잡도O(n), 공간복잡도O(1)

 

결과