잡담
간혹 알고리즘 문제를 풀다보면 로직에는 아무 이상이 없다고 생각했는데, 테스트케이스를 통과하지 못할때가 있다. 킹받는건 프로그래머스의 테케는 공개되지 않기 때문에, 해당 fail을 일으키는 케이스들을 내가 찾아야한다. 그래서 그런지 난이도가 올라갈수록 오히려 공개된 테케에서 빨간글이 더 반가울 때가 많다.
아직 미숙한 내가 엣지케이스를 잘 못찾는 이유는,
- 문제를 꼼꼼히 읽지 않은 경우
- 로직이 문제가 요구하는 모든 케이스를 담고있지 않은 경우이다.
엣지케이스를 찾아내는 것이 중요하다고 생각되는 이유는, 웹 프론트엔드 개발에서 실력이라고 말할 수 있는것중 하나가 이러한 케이스들을 꼼꼼하게 관리하여 에러핸들링을 잘 하는 것이기 때문이다.
우선 문제를 보자면,
입출력 예를 본다면 10억개의 도로에 1천만개의 블록을 까는 문제이다. 당연히 해당 문제를 부루트 포스로 구한 후 begin부터 end 를 잘라내는 방식은 효율성 테스트를 통과하지 못한다.
내 풀이
function solution(begin, end) {
const makeBlock = (num) =>{
if(num === 1) return 0;
let last = 0;
for(let i = 2; i*i<=num; i += 1){
if(num % i === 0){
last = i;
if(num / i <= 10000000) return num/i;
};
};
if(last === 0) return 1;
return last;
};
let result = [];
for(let i = begin; i <= end; i += 1){
result.push(makeBlock(i));
};
return result;
};접근한 방식
해당문제의 패턴은 입출력예에 나와있다. 숫자블록의 배수간격마다 블록이 깔린다면, 어떤 수가 소수가 아니라면 어떤수의 약수중 가장 큰 수가 깔리며 소수라면 1이 깔린다는 것이다.
패턴을 찾았으니 해당 숫자를 소수엔 1을, 약수가 있다면 가장 큰 약수를 리턴하는 함수를 만들면 된다.
놓치고 있던 점
계속해서 케이스를 통과하지 못했는데, 문제는 10억개의 도로에 깔리는 숫자는 1천만까지의 숫자가 깔리기 때문이다. 그래서 어떤 구간이 나올때, 그 구간의 숫자 중 약수가 천만이 넘어가는게 있다면 천만이 넘지않는 그 다음 수를 return을 해야했다.
이는 어렵지 않았던 것이 약수를 찾기위해 숫자를 순회할때, 천만이 넘지 않을때 return 한다면 어렵지 않게 구할 수 있었다.
여기까진 잘 해결했는데, 계속해서 통과되지 못하는 케이스가 있었다. 그래서 생각해보니 찾아낸 케이스가 만약,
'50000095' 라면 약수는 두개의 소수인 [5, 10000019] 이다. 이는 효율성을 위해 제곱근 까지 탐색해야만 하는 조건에서라면 구할 수가 없는 수이다.
그래서 고민해서 내린답은 아래와 같다.
function solution(begin, end) {
const makeBlock = (num) =>{
if(num === 1) return 0;
let last = 0;
for(let i = 2; i*i<=num; i += 1){
if(num % i === 0){
last = i;
if(num / i <= 10000000) return num/i;
};
};
if(last === 0) return 1;
return last;
};
let result = [];
for(let i = begin; i <= end; i += 1){
result.push(makeBlock(i));
};
return result;
};항상 엣지케이스를 잘 생각하자...
짝수에는
