제한 조건이 뭐냐에 따라 다르죠. 메모리를 O(n)만큼 써도 된다면 원소를 키로, 원소의 등장 회수를 값으로 하는 해쉬 테이블을 쓰면 됩니다. 메모리가 O(1)이지만 시간복잡도가 O(n*n)이어도 된다면 당연히 i in [1, N-1]에 대해, i+1부터 N번째까지 원소 중에 i번째 원소와 같은 게 있는지 보면 됩니다. 메모리는 O(1)이지만 시간복잡도는 그보다 좋아야 하면 in-place sorting 같은 것을 써서 정렬을 하고 정렬된 배열을 처음부터 끝까지 한 번 살펴보면 됩니다. 배열의 원소나 중복이 일반적인 게 아니라 특별한 조건을 만족시킨다면 훨씬 더 효율적인 알고리즘이 있을 수도 있습니다.
...
제한 조건이 뭐냐에 따라 다르죠. 메모리를 O(n)만큼 써도 된다면 원소를 키로, 원소의 등장 회수를 값으로 하는 해쉬 테이블을 쓰면 됩니다. 메모리가 O(1)이지만 시간복잡도가 O(n*n)이어도 된다면 당연히 i in [1, N-1]에 대해, i+1부터 N번째까지 원소 중에 i번째 원소와 같은 게 있는지 보면 됩니다. 메모리는 O(1)이지만 시간복잡도는 그보다 좋아야 하면 in-place sorting 같은 것을 써서 정렬을 하고 정렬된 배열을 처음부터 끝까지 한 번 살펴보면 됩니다. 배열의 원소나 중복이 일반적인 게 아니라 특별한 조건을 만족시킨다면 훨씬 더 효율적인 알고리즘이 있을 수도 있습니다.
댓글 달기