반응형
1. 문제
- n개의 요소로 이루어진 배열 nums가 주어질 때, nums[i]는 1~n 사이에 존재하는 경우, 누락된 정수 배열을 반환하라.
2. 해결
function findDisappearedNumbers(nums: number[]): number[] {
const set = new Set(nums);
const max = Math.max(...set);
for(let i = 1; i<=nums.length; i++){
if(set.has(i)) set.delete(i);
else set.add(i)
}
return [...set];
};
- 처음 풀이할 때 방식이다.
- Set을 이용해 중복을 제거하고, 1부터 n까지 반복하며 목록을 갱신해준다.
- 이렇게 하니까 시간이 상당히 오래걸려서 다른 사람 풀이도 한 번 봤다.
function findDisappearedNumbers(nums: number[]): number[] {
for(let i=0;i<nums.length;i++)
if(nums[Math.abs(nums[i])-1]>0)
nums[Math.abs(nums[i])-1]*=-1;
let arr = [];
for(let i=0;i<nums.length;i++)
if(nums[i]>0)
arr.push(i+1);
return arr;
};
- 다른 사람의 풀이 방법인데, 뭔 소린지 이해가 안갔다.
- 일단, 인덱스 마킹 기법이라는 걸 사용했는데, 원리는 해당 요소 -1 인덱스의 값을 음수 처리하여 해당 값이 있다는 걸 표현한다고 한다.
[4,3,2,7,8,2,3,1]
- 이 예시의 경우
index | element |
0 | 4 3 2 -7 8 2 3 1 |
1 | 4 3 -2 -7 8 2 3 1 |
7 | -4 -3 -2 -7 8 2 -3 -1 |
- 이렇게 배열 요소 값이 변경되고, 다시 반복하면서 양수인 요소의 인덱스 값 +1인 애들이 없는 정수의 집합이 된다고 한다.
- ... 어렵다.