[프로그래머스] 짝지어 제거하기

Hyebin·2021년 8월 11일
0

Data structure / Algorithm

목록 보기
15/19
post-thumbnail
post-custom-banner

문자열에서 같은 알파벳 2개를 찾고, 그 짝을 제거한 후 앞뒤로 문자열을 붙이는 과정을 반복해서 문자열을 모두 제거하는 문제이다.
성공한다면 1, 아니면 0을 리턴하면 된다.

자세한 문제 보기는 아래 링크로!
https://programmers.co.kr/learn/courses/30/lessons/12973

첫번째 시도

아주 단순하게 생각해서 앞뒤 문자열이 같을 때 제거해서 붙여가는 식으로 풀면 되지 않나하고 풀었지만 같은 짝을 찾아 제거 후에 다시 인덱스 0부터 탐색을 하는 구조라 효율성에서 다 시간초과로 실패;;ㅎ

코드

  • 문자열을 순회하며 2개가 붙어 있는 짝 찾기
  • 문자열에서 그 둘 제거 후 문자열 붙이기
function solution(s) {     
    let arr = s = s.split('')
    for(let i=0; i<arr.length; i++) {
        if(arr[i] === arr[i+1]) {
            arr.splice(i,2)
            i = -1
        }
    }
    
    return arr.length === 0 ? 1 : 0
}

정답 풀이

스택을 이용하여 풀면 스택에 들어간 값과 현재 문자만을 비교하면 되서 문자열의 길이만큼만 순회하면 된다.

코드

  • 문자열 s를 순회
  • 스택의 최상위 값과 현재 문자가 같지 않으면 스택에 추가
  • 같다면 스택에서 최상위 값 제거
function solution(s) {  //baabaa
    //스택 - 선입후출
    //스택의 최상위 값과 현재 문자가 같지 않으면 스택에 추가 
    //같다면 스택에서 제거한다.

    let stack = []  
    
    for(let i=0; i<s.length; i++) { 
        if(stack[stack.length-1] !== s[i]) stack.push(s[i])
        else stack.pop()
    }
    
    return stack.length === 0 ? 1 : 0
}
post-custom-banner

0개의 댓글