ㅠㅠ.. 많이 공부하고 있다고 생각했지만 아직 멀었다..고 또 느낀다. 사실 어제 블로그 포스팅을 2문제는 하겠다며 호기롭게 공부를 시작했지만 현실은 ..3시간이 걸려도 1문제도 풀지 못했다.😂 휴.. 그래도 해야지 뭐 어쩌겠나, 다음 날이 되어서 다시 푸는 것을 시도했지만 이것은 내 구현실력의 문제라 판단하여 다른 분들의 답안지를 보았다. 그런데 보아도 이게 무슨말이지.. 재귀에 대해 알고있다고 생각했는데 아직은 멀었다는 것을 느낀다.. 그리고 또 이 문제를 간단명료하게 풀어내는 다른 분들에 대해 존경심도 생겼다.. 내가 막혔던 문제는 소수찾기 문제이다.
소수찾기
문제의 로직을 세우는 건 간단했다. 실제 다른 분들의 로직 역시 같았다 그렇지만 구현을 해내는데 차이가 났다.
먼저 내가 세우 로직은 다음과 같다.
- 주어진 수 (number)로 만들 수 있는 수를 모두 만든다. (순서 중요)
- 그 다음 중복을 제거한다. (new Set이용)
- 배열을 순회하며 해당 숫자의 소수를 판단한다.
이렇게 하면 됐다. 1. 번의 로직을 구현하는 것이 내겐 너무 어려웠다. 재귀를 사용하려 해보았다.
이렇게 하려면 재귀를 할 때마다 조건식에서 방문하지 않은 index를 기억해야한다고 생각했다. 그런데 이를 구현해보려하니 쉽지않았다.. 결국 이건 순열을 구해야하는 문제인데 순열을 어떻게 구할수있나 코드를 찾아보았다.
function solution(numbers) {
var answer = 0;
var n = numbers.split('');
var nums = new Set()
combi(n,'');
function combi(a, s) {
if (s.length > 0) {
if (nums.has(Number(s))=== false) {
nums.add(Number(s));
console.log(Number(s))
if (chkPrime(Number(s))) {
answer++;
}
}
}
if (a.length > 0) {
for (var i = 0; i< a.length; i++) {
var t = a.slice(0)
t.splice(i,1);
//console.log(t)
combi(t,s + a[i]);
}
}
}
function chkPrime(num) {
if (num < 2) return false;
if (num === 2) return true;
for (var i = 2; i <= Math.sqrt(num); i++) {
if (num%i===0) return false;
}
return true;
}
return answer;
}이건 다른 분이 풀어주신 코드이다. splice와 slice를 사용해 구현을 한거 같은데 아직은 이해가 되지 않는다...
재귀함수도 사용하신 거 같은데 천천히 코드를 보고 순서를 짐작해보아야겠다. 더 공부해보고 추가로 포스팅을 할 것이다.
그래도 꼭 이해에 성공한 뒤 포스팅을 하고싶다.
도움을 받을 유튜브
큰수만들기
필자가 계속 실패했던 문제는 순열이나 조합의 문제인 경우가 많아. 이를 공부한 뒤 다시 푸는 것으로 하고 필자는 일단 순열이 필요없는 문제를 찾아 해결해보려하였다.
위 문제는 처음엔 그냥 큰순서대로 정렬한다음 k만큼 자르면되지 않나? 라고 생각을 했는데 이는 오류였다.
문제를 다시 읽어보면 위치는 그대로이고 k만큼 삭제를 하는 경우와 같다. 즉, 주어진 순서에서 최대값을 만들 수 있도록 k개 잘랐을 때의 남은 number를 return하면된다.
로직을 다음과 같이 수정하였다.
- Stack을 이용해보자
- 기본적으로 stack에 쌓고 다음 큰 수가 나온다면 pop 후 push 인데 여기서 문제는
- stack의 길이와 남은 number의 길이의 합이 number-k(잘려지는 수의 길이) 와 같다면 그땐 그냥 남은 number를 다 stack에 넣어버리자
그런데 이렇게만 풀어버리니 예를들어 41772526 에서 k 가 5인경우 477 이 리턴된다.
하지만 실제 정답은 776이 나와야한다. 그렇게 아 ! 뭔가 비교하는 게 잘못되었구나 로직을 수정해야겠다고 생각했다. 로직에 오류가 있다. 3번 역시 논리적이지 못하다.
하지만 위 로직대로 문제를 풀었을 때 테이스 케이스는 통과할 수 있다.
let number = "4177252841";
let K = 4;
function solution(number, K) {
const numLength = number.length;
const first = number.slice(0, number.length - K).split(``);
const Max = String(Math.max(...first));
const MaxIndex = number.split(``).indexOf(Max);
let numberArr = number.split(``);
numberArr = numberArr.splice(MaxIndex);
number = numberArr.join(``);
let stack = [Max];
let answer = ``;
for (let i = 1; i < number.length; i++) {
const lastIndex = stack.length - 1;
if (stack.length + number.length - i === numLength - K) {
const lastnumber = number.substr(i);
console.log(lastnumber);
answer = [...stack, lastnumber];
return answer.join(``);
}
if (stack[lastIndex] < number[i]) {
stack.pop();
stack.push(number[i]);
continue;
}
stack.push(number[i]);
}
return stack.join(``);
}
solution(number, K);한 눈에 보아도 좋지 않고 논리적이지 못하다. 위 순열을 공부하면서 위 문제도 꼭 다시 풀어보겠다.
다음 포스팅을 내일까지 업데이트하겠다!
