[Programmers] 짝지어 제거하기 - JavaScript

Joosi_Cool·2023년 2월 9일
0

Programmers

목록 보기
13/98
post-thumbnail

문제설명



설계 과정

  • 현 요소가 다른 요소랑 같은가?
    -> 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 과 같은 방법을 생각해내고, 구상할 수 있냐에 문제였다.



결과

profile
집돌이 FE개발자의 노트

0개의 댓글