Tasks
N개의 정수로 구성된 비어 있지 않은 배열 A가 제공됩니다. 배열에는 홀수 개의 요소가 포함되어 있으며 배열의 각 요소는 짝을 이루지 않은 하나의 요소를 제외하고 동일한 값을 가진 다른 요소와 쌍을 이룰 수 있습니다.
예를 들어 배열 A에서 다음과 같습니다.
A[0] = 9 A[1] = 3 A[2] = 9
A[3] = 3 A[4] = 9 A[5] = 7
A[6] = 9
인덱스 0과 2의 요소는 값이 9이고,
인덱스 1과 3의 요소는 값 3을 가지며,
인덱스 4와 6의 요소는 값 9를 가지며,
인덱스 5의 요소는 값이 7이고 짝이 없습니다.
함수 작성:
기능 솔루션(A);
위의 조건을 충족하는 N개의 정수로 구성된 배열 A가 주어지면 짝을 이루지 않은 요소의 값을 반환합니다.
예를 들어 다음과 같은 배열 A가 있다고 가정합니다.
A[0] = 9 A[1] = 3 A[2] = 9
A[3] = 3 A[4] = 9 A[5] = 7
A[6] = 9
함수는 위의 예에서 설명한 대로 7을 반환해야 합니다.
다음 가정에 대한 효율적인 알고리즘을 작성하십시오 .
N은 [1..1,000,000] 범위 내의 홀수 정수이고;
배열 A의 각 요소는 [ 1 .. 1,000,000,000 ] 범위 내의 정수입니다 .
A의 값 중 하나를 제외한 모든 값이 짝수 번 발생합니다.
내 풀이
Set
- set 객체는 중복되지 않는 유일한 값들의 집합이다.
- set 객체는 다음과 같은 특징을 가진다.
1. 동일한 값을 중복하여 포함할수 없다
2. 요소 순서에 의미가 없다
3. 인덱스로 요소에 접근할 수 없다.
이러한 set 객체는 수학적 집합을 구현하기위한 자료구조이다.유용한 문법
set.add (추가) | set.delete (삭제) | set.clear() (전체 비우기) | set.has (존재여부확인)
특별한 사실
set은 이터러블이기 때문에 for..of문으로 순회도 가능하고, 스프레드 문법과, 배열 디스트럭처링의 대상이 될 수도 있음
// 이터러블인 Set 객체는 for...of 문으로 순회할 수 있다. for (const value of set) { console.log(value); // 1 2 3 } // 이터러블인 Set 객체는 스프레드 문법의 대상이 될 수 있다. console.log([...set]); // [1, 2, 3] // 이터러블인 Set 객체는 배열 디스트럭처링 할당의 대상이 될 수 있다. const [a, ...rest] = [...set]; console.log(a, rest); // 1, [2, 3]한참을 고민하다가.. 테스트 케이스가 최대 100만개, A의 값이 최대 10억인 걸 알면서도 for로 풀어보았다가 당연히 0점을 맞았다.
코드는 예상이 갈테니 생략하도록 하고
다른 사람의 풀이를 보자
결론적으로 set을 활용하여 객체로 풀었다.
function solution(A) {
// 빈 set을 element에 할당
let element = new Set();
// for in은 객체의 반복문에서 활용
// 자바스크립트에서는 배열도 Object로 인식하기 때문에 가능
// 객체에서 할당을 확인하기 위한 것이니 in을 사용해야함 of사용시 에러
for (let v in A) {
if (!element.has(A[v]) {
element.add(A[v]);
} else {
element.delete(A[v]);
}
}
const result = [...element];
return result[0];
}결과
