이번 문제는 짝지어 제거하기이다.
앞뒤의 문자가 같은 문제일때 제거할수있다.
예시로 'baabaa'가있으면 b와 a를 처음 비교하고 다르니
두번째인자로 넘어간다.
2번째 a와 3번째 a가 같으니 짝지어 제거할수 있다.
제거하면 다시 앞에서 부터 비교를 시작하여 같다면 제거할수 있다.
bbaa 가되었으니 bb , aa 다 제거 가 가능하다
다 제거가 가능하면 1을 리턴 아니면 0을 리턴하면 된다.
1차 풀이
1차때 단순히 앞뒤 비교를 하고 맞으면 제거하고 다시 앞에서 부터 다시 체크하도록 하는 로직을 생각했다. 앞선 문제에서 재귀함수에 대해서 배워서 재귀함수를 써보자 생각을 하게 되었다.
레벨 2의 소수찾기 문제였는데 확실히 어렵다.. 나중에 풀어보기 위해서 벨로그에 아직 적지는 않았다. 재귀함수를 써서 풀어보려고 했는데 무한 루프의 공격에 맞아버렸다..
적잖이 멘붕을 하고 다시 문제를 풀어보려고 해도 다른 방법은 떠오르지 않아서 힌트를 찾아보게 되었다.
힌트로 얻은 것은 스택과 큐로 문제를 푸는 것..
2차 풀이
스택과 큐에 대해서 알게 되었고 적용하게 되었다.
- 문자 하나를 떼서 비교를 해야 한다. 스택이라는 배열을 만들어두고
배열이 비어있을 경우 혹은 다음순서의 문자와 비교했을때 같지 않다면 배열에 저장해둔다.- 만약 배열안에 넣어놓은 문자와 그다음 순서의 문자가 같다면 배열에 담아둔것을 제거해준다.
코드를 보면 이렇다.
function solution(s)
{
let stack = [];
for(let i=0; i<s.length;i++){
let cue = s.slice(i,i+1)
if(!stack.length||stack[stack.length-1]!==cue){
stack.push(cue)
}else{
stack.pop()
}
}
return stack.length?0:1
}꽤 단순하게 문제가 풀렸다..
이런 사고방식으로 빨리 어떻게 접근할지 체크해야 하는데 아직 모자란것 같다..
또하나 드는 생각은 알고리즘 문제도 결국 하나의 기법(스택,큐 ) 이런 것으로 돌려막기 하는 느낌이 든다.. 기법들을 짜맞춰서 풀어야 하고 정해진 공식이 있는것 같다는 생각이 든다.
막무가내로 풀면 안되고 공식들을 빨리 배워서 이럴때 이런 공식을 대입하고 하는 능력이 필요한것 같다.
다음에도 다시 풀어봐야 할 문제인것 같다.
