문제 링크
문제
문제 간단 설명
배열이 2개(a,b) 주어진다. 각각의 a배열 요소의 제곱이 b배열 요소에 속할 때, 최종 결과값으로 true를 리턴한다. 만약 b배열의 요소 중에 a배열 요소의 제곱이 1개라도 없는 경우 false를 리턴한다.
- 예시1
a = [121, 144, 19, 161, 19, 144, 19, 11]
b = [121, 14641, 20736, 361, 25921, 361, 20736, 361]위의 두 배열을 문제의 조건에 맞춰 알기 쉽게 나타내면 아래와 같다.
a = [121, 144, 19, 161, 19, 144, 19, 11]
b = [11*11, 121*121, 144*144, 19*19, 161*161, 19*19, 144*144, 19*19]최종적으로 위 두 배열의 계산 결과는 true이다.
- 예시2
a = [121, 144, 19, 161, 19, 144, 19, 11]
b = [132, 14641, 20736, 361, 25921, 361, 20736, 361]
위의 배열에서 b배열의 132는 어떠한 a배열의 요소의 제곱이 아니기 때문에 결과값은 false이다.
- 조건
- 주어지는 두 배열은 빈 배열일 수 있다.- 주어지는 두 배열은 null값을 가질 수 있다.
- 둘 중 하나의 배열이 null값이라면 결과값은 false를 반환한다.
문제 접근
이 문제는 가장 기본적인 생각은 이중 for문으로서 각각의 a배열을 순회하면서 그 안에 a배열 요소의 제곱이 b배열 요소 안에 존재하는지 확인하는 방법이였다. 그런데 이 방법엔 오류가 있다. 예를 들어 a배열의 11이 2개 존재하면, b배열에도 그의 제곱인 121도 2개 존재해야한다. 하지만 위에 처럼 코드를 구현하면 121이 1개만 존재해도 true가 나오게 된다.
그렇다면 어떻게 접근해야할까? 배열 안에서 무언가를 찾아야 할 때, 정렬에 대해서 생각하게 된다. 정렬이라는 것은 단순하게 크키순으로 나열하는 것만을 의미하지 않는다. 배열 안에서 무엇가를 찾을 때, 내가 원하는 것을 단순 찾기보다 좀 더 빠르게 찾을 수 있는 수단을 제공한다. 위의 문제도 a배열 요소의 제곱을 b배열에서 찾는다는 관점에서 보면 우선 정렬을 하는 것은 좀 더 빨리 찾기 위한 방법이 될 수 있다. 또한 정렬을 하게 되면, 순서대로 a배열과 b배열이 맵핑됨을 알 수 있다. 이것은 인덱스값이 같으면 b배열(요소)은 a배열(요소)의 제곱의 관계에 있다고 말할 수 있는 것이다.
이렇게까지 문제를 생각하고 풀이하였으나, 가장 문제되는 부분은 바로 조건 부분이였다. null값과 빈 배열의 처리는 어떻게 해야 할 것인가?
null값과 빈 배열에 대해서 다시 정리해보면 아래와 같다.
a b return
null null false
null null X false
null X null false
[] [] true
[] [] X false
[] X [] false조건을 어떤 식으로 나눠야 할지 고민하였다. 그래서 그냥 null값인 경우, 배열.length==0인 경우를 모두 나누어 생각하였다. 뭔가 깔끔하진 않았지만 가장 명료하다고 해야할까?!
1 function comp(array1, array2){
2 if(!array1 || !array2) return false;
3 else if(!array1.length && !array2.length) return true;
4 else if(!array1.length || !array2.length) return false;
5 else{
6 array1.sort((a,b)=>a-b);
7 array2.sort((a,b)=>a-b);
8 return array2.every((ele, idx) => (ele === Math.pow(array1[idx], 2)));
9 }
10 } 2,3,4번 라인이 위의 null값과 빈배열에 대한 조건을 나눠 놓은 코드이다. 2번라인은 배열이 null인지 아닌지를 구분하는 것이고 3,4번라인 어떤 배열이 빈배열인지에 따라서 조건을 나눠놓은 것이다. 빈배열을 따져야하는 이유는 every()는 빈배열이 들어가는 경우 순회하지 않고 true값을 리턴한다. 만약에 a = [] , b = [121, 144]라면 결과값이 말도 안되게 true가 나온다. 이런 예들을 방지하기 위해서 배열 중에 하나만 length가 0인 경우를 골라야 한다. 그런데 !array1.length || !array2.length 코드는 모두 length가 0인 경우도 포함한다. 이와 같은 경우는 true가 되어야하기에 그 윗줄에 먼저 조건을 거를 수 있도록 적어준 것이다.
Best Solution
function comp(array1, array2) {
if(array1 == null || array2 == null) return false;
array1.sort((a, b) => a - b); array2.sort((a, b) => a - b);
return array1.map(v => v * v).every((v, i) => v == array2[i]);
}
가장 투표를 많이 받은 풀이이다. 그런데 사실 그렇게 좋은 풀이라는 생각은 안든다. 이유는 두 가지다. 첫번째는 효율성에 있다. 정렬을 했음에도 비교하는데 있어서 순회를 2번했다. map()을 통해서 제곱으로 값을 바꾸고 다시 그 값을 array2와 비교하였다. 두번째는 조건을 모두 충족시켜주지 않았다. 첫번째 효율성 문제는 논외라고 치더라고 이 문제는 반드시 생각했어야만했다. 그것은 빈 배열일 때의 조건을 생각하지 않았다. 위의 풀이에서 array1= [], array2 = [121, 14641, 20736] 이면 결과값이 true가 나온다. 사실은 false여야 맞는 값이다. 그런데 왜 이게 풀이를 통과했는가? 사실 그건 codewars의 샘플테스트 시스템에 있다. 여기서는 공적으로 만든 문제들도 있는가하면 그냥 일반인이 문제를 만들어서 베타테스트를 거쳐서 문제가 탄생하는 경우도 있다. 즉 오픈소스 알고리즘 문제인 것이다. 수백명, 수천명이 문제를 접하면서 의견을 내고 그 의견을 바탕으로 수정을 거쳐서 문제가 나오게 된다. 그 과정 중에 테스트 예시가 누락되어서 아마 저런 풀이도 통과 되는 것 같다. 주어진 배열이 [], null or null, []인 경우까지는 테스트 샘플로 주어져있는 것을 확인했지만 위에서 언급한 예시는 없었다. 사실 아마도 너무 당연해서 넣지 않은 것 같다. 위의 문제에서도 If a or b are empty then the result is self-evident.라고 명시해 놓은 것을 보면 말이다. (self-evident : 자명한)
결론
매일 남의 풀이만 보고 감탄을 하다가 틀린 부분에 대해서 지적(?)을 하니 뭔가 대단한 것을 한 것 같지만, 사실 의문을 가져야 할 부분에 대해서 의문을 가졌다고 본다. 그리고 그 부분에 대해서 찾아보고 확인하였을 뿐이다. 나 말고도 이런 의문을 품은 사람들이 있다는 것은 어찌보면 나한테는 감사하고 고마운 일인 것 같다. 나의 생각에 확신을 주었기 때문이다. 오늘은 이러한 오류는 찾은 것만으로도 만족한다! 끝!😎
