- 현 요소가 다른 요소랑 같은가?
-> yes : 그 둘을 삭제 -> 처음으로 다시
-> no : 다음 요소로 이동- 끝까지 돌았거나, 입력받은 문자열의 길이가 2미만이라면?
-> 문자열의 길이 = 0 인지 체크
-> yes: 1 반환
-> no : 0반환
function solution(s)
{
//문자를 배열로 변경
s = s.split("");
//계속 반복
while(true){
//s를 하나씩 체크
for(var index = 0;index<s.length-1;index++){
//현 요소와 다음 요소가 같은지 확인
if(s[index]===s[index+1]){
// 같다면 그 부분을 잘라내고 처음으로 다시 돌아감.
s.splice(index,2);
console.log(s);
break;
}
}
//끝까지 같거나 s의 길이가 2미만이면 체크해준다.
if(index === s.length-1 || s.length<2 ){
//길이가 0으로 모든게 삭제됬다면 1 반환
if(s.length === 0 ){
return 1;
}
//뭐가 남아 있다면 0으로 반환
else{
return 0;
}
}
}
}
결과는 처참했다... 우선 코드에 시간복잡도가 너무 높은 것 같다. while문을 써서 하나씩 확인해주는 습관은 매우 좋지않다. 이보다 더 시간복잡도가 좋은 코드를 만들어내야 한다.
고민을 많이 해본 결과, stack
이라는 개념을 이용하기로 했다.
- stack 생성
- s문자열을 하나씩 보면서 체크
-> stack 마지막 요소와 넣을려는 문자열이 같다면 pop
-> 다르다면 push- 마지막에 stack에 남아 있는게 있다면 0, 없다면 1 반환
function solution(s)
{
var stack = [s[0]];
for(var index = 1; index<s.length;index++)
{
//stack에 마지막 요소와 넣을 값이 같다면 마지막 요소 제거
if(stack[stack.length-1]===s[index]){
stack.pop();
}
else{
stack.push(s[index]);
}
}
if(stack.length === 0){
return 1;
}
else{
return 0;
}
}
stack을 하나 만들어놓고, 문자열 s를 이에 넣으면서 마지막 요소와 넣을 요소가 같다면 pop 해주는 방식으로 진행했다. 이렇게 하니 코드도 그렇고 시간복잡도도 엄청나게 줄일 수 있었다.
이번 문제는 처음처럼 노가다 느낌으로 하나씩 찾는 것이 아니라 stack 과 같은 방법을 생각해내고, 구상할 수 있냐에 문제였다.