문제
A non-empty array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.
For example, in array A such that:
A[0] = 9 A[1] = 3 A[2] = 9
A[3] = 3 A[4] = 9 A[5] = 7
A[6] = 9
the elements at indexes 0 and 2 have value 9,
the elements at indexes 1 and 3 have value 3,
the elements at indexes 4 and 6 have value 9,
the element at index 5 has value 7 and is unpaired.
Write a function:
function solution(A);
that, given an array A consisting of N integers fulfilling the above conditions, returns the value of the unpaired element.
For example, given array A such that:
A[0] = 9 A[1] = 3 A[2] = 9
A[3] = 3 A[4] = 9 A[5] = 7
A[6] = 9
the function should return 7, as explained in the example above.
Write an efficient algorithm for the following assumptions:
N is an odd integer within the range [1..1,000,000];
each element of array A is an integer within the range [1..1,000,000,000];
all but one of the values in A occur an even number of times.
문제풀이
배열의 총 길이는 홀수이고, 요소의 짝은 모두 짝수인데 그 중 홀수로 이루어진 요소를 찾는 문제이다.
처음에 문제를 읽고 값이 +2의 값과 동일하지 않은 값을 찾다가 모두 Wrong Answer가 떠서 다시 문제를 읽어야 했다.
배열의 길이는 홀수이며, 모든 값이 짝수로 이뤄져 있는데 그 중 값의 갯수가 홀수인 것을 찾는 것
풀이과정
오브젝트를 사용해 값을 지정하고 같은 값이 있다면 value를 하나씩 삭제한다. value가 1보다 작다면 key 자체를 삭제해 요소가 짝수라면 오브젝트에서 사라지고 홀수인 요소만 남게 된다.
- 오브젝트를 사용해 요소를 값으로 지정
- 지정된 값이 있다면 value를 하나씩 삭제 (1개라면 key자체를 삭제)
- 오브젝트에 남은 홀수 값을 답으로 지정
코드
function solution(A) {
let answer = 0;
let obj = {};
for(let i = 0; i<A.length; i++){
if(obj[A[i]]) {
if(obj[A[i]] > 1) obj[A[i]] -=1
else delete obj[A[i]]
}
else{
obj[A[i]] = 1
}
}
answer = Object.keys(obj)
return Number(answer[0])
}
최종결과
처음에 오브젝트에 내용을 저장하고 오브젝트를 돌면서 2로 나눈 나머지 값이 0이 아닌 key 값을 찾는 방식의 코드를 짰는데 timeout error가 떴다.
좀 더 효율적인 코드를 짤 수 있는 방법에 대해서 고민할 필요가 있다고 느꼈다.
출처
