문제링크
문제
Your goal in this kata is to implement a difference function, which subtracts one list from another and returns the result.
It should remove all values from list a, which are present in list b.
arrayDiff([1,2],[1]) == [2]If a value is present in b, all of its occurrences must be removed from the other:
arrayDiff([1,2,2,2,3],[2]) == [1,3]🚩 문제설명
어제 푼 문제와 같은듯 다른 문제!
(참고 Remove duplicate words)
배열이 2개 주어지는 a배열에서 b배열의 요소를 제거한 새로운 a'배열을 만드시오!!
문제접근
처음에 실수한 부분이 b배열의 요소가 항상 1개라고 단정지었던 부분이었다. b배열에도 1개이상의 원소가 존재할 수 있다는 점을 생각해야한다. 그렇게 되면 이 문제는 이중반복을 해야만 한다고 생각했다.(Best Solution에서 보면 이중반복을 피하는 풀이들이 있다.) 배열 메소드를 사용하더라고 이중반복을 피할 수 없다. 내 풀이는 단순하게 이중for문을 사용하여 풀이하였다.
isDiff라는 boolean타입의 변수를 사용한 이유는 a배열의 요소가 b배열의 요소와 같은지 다른지를 체크하여 result배열에 추가 여부에 대한 flag가 필요했기 때문에 사용하였다.
1 function arrayDiff(a, b) {
2 const result = [];
3 for(let i = 0; i < a.length; i++){
4 let isDiff = true;
5 for(let j = 0; j < b.length; j++){
6 if(a[i] === b[j]) {
7 isDiff = false;
8 break;
9 }
10 }//for j
11 if(isDiff) result.push(a[i]);
12 }//for i
13 return result;
14 }좀 더 직관적이고 쉽게 풀 수 있는데, 푸는 당시에는 별 생각이 들지 않았다😭...밑에 좋은 풀이들을 첨부한다.
Best Solution
- 첫번째 풀이
function array_diff(a, b) {
return a.filter(function(x) { return b.indexOf(x) == -1; });
}마찬가지로 이중순회를 하지만 훨씬 더 간편하고 직관적이다.
- 두번째 풀이
function array_diff(a, b) {
const set = new Set(b)
return a.filter(x => !set.has(x))
}b배열을 Set객체로 바꿔서 has()메소드를 통해서 직접 접근함으로서 복잡도를 낮추었다.
- 세번째 풀이
function array_diff(a, b) {
var bDict = {}; // Empty object
b.forEach(i => bDict[i] = true); // Create a key for each element in b
return a.filter(i => !bDict[i]); // Filter out elements which are keys in the dict
}개인적으로 이 풀이가 가장 인상 깊었다. 하나의 배열로 객체를 생성하고 다른 배열로 그 객체에 접근하는 방법을 통해서 배열 안에 요소 존재 유무를 판별하였다. 👍
결론
빅오표기법으로 풀이를 좀 따져보자.
내 풀이와 Best Solution의 첫번째 풀이는 O(a*b) => O(n*n) = O(n^2)
Best Solution의 두번째 풀이는 O(n)
Best Solution의 세번째 풀이는 O(a+b) => O(n+n) => O(2n) = O(n)시간복잡도로 따지면 두번째와 세번째 풀이가 가장 좋음을 알 수 있다. 그런데 코드의 performance를 확인하는 사이트에서 위 4가지를 돌려서 비교해보면 엄청나게 차이가 나지는 않는다는 결과가 나온다. 왜 그런 결과가 나오는지는 정확히 알 수는 없지만, 결론은 O(n^2)이 가장 느린 것은 맞다.
아직 코드의 효율성이나 그런부분에 있어서 미숙한 점이 있다. 나름 여러가지 생각을 해보려고 하지만 알고리즘에 대한 내공이 많이 부족한 것 같다. 이런 부분을 잘 파악하고 좀 더 효율적인 코드를 잘짜는 방법은 무엇인지 고민해봐야겠다.
