Minimum Number of Operations to Make Elements in Array Distinct
EasyArrayHash Table
문제 설명
- 정수 배열
nums가 주어집니다. - 모든 요소를 유일하게 만들기 위한 최소 작업 횟수를 반환합니다.
- 작업은 배열의 앞부분에서 최대 3개의 요소를 제거하는 방식입니다.
- 배열이 비어있으면 모든 요소가 유일한 것으로 간주됩니다.
문제 풀이
Hash Table
Map객체를 활용하여 배열의 각 요소가 몇 번 등장했는지 추적합니다.- 모든 요소의 등장 횟수가 1 이하가 되면 배열의 모든 요소는 유일합니다.
- 배열의 앞부분에서 최대 3개의 요소를 반복적으로 제거하며, 모든 요소가 유일해질 때까지 작업을 수행합니다.
- 해당 작업의 횟수를 반환합니다.
export function minimumOperations(nums: number[]): number {
const n = nums.length;
const counter = new Counter(nums);
let i = 0;
let answer = 0;
while (!counter.isDistinct() && i < n) {
for (const num of nums.slice(i, i + 3)) {
counter.sub(num);
}
i += 3;
answer += 1;
}
return answer;
}
class Counter extends Map<number, number> {
constructor(nums: number[]) {
super();
nums.forEach((num) => {
this.add(num);
});
}
get(num: number): number {
return super.get(num) ?? 0;
}
add(num: number): this {
return super.set(num, this.get(num) + 1);
}
sub(num: number): this {
return super.set(num, this.get(num) - 1);
}
isDistinct(): boolean {
for (const count of this.values()) {
if (1 < count) {
return false;
}
}
return true;
}
}복잡도
- 시간 복잡도:
- 공간 복잡도:
Reverse Traverse
- 배열을 뒤에서 부터 순회하며, 이미 확인된 요소는
Set에 추가합니다. - 만약 현재 요소가 이미
Set에 존재한다면, 처음부터 현재 요소까지 제거해야합니다.- 따라서, 작업 횟수는 해당 위치를 기준으로, 이 됩니다.
- 중복이 없으면
0을 반환합니다.
export function minimumOperations(nums: number[]): number {
const n = nums.length;
const set = new Set<number>();
for (let i = n - 1; i >= 0; i--) {
if (set.has(nums[i])) {
return Math.floor(i / 3) + 1;
}
set.add(nums[i]);
}
return 0;
}복잡도
- 시간 복잡도:
- 공간 복잡도: