[프로그래머스] Lv.2 짝지어 제거하기 / JavaScript

이희령·2023년 10월 22일

알고리즘

목록 보기

3/20

문제 설명

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.

예를 들어, 문자열 S = baabaa 라면

b aa baa → bb aa → aa →

의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

입출력 예

s	result
baabaa	1
cdcd	0

입출력 예 #1
위의 예시와 같습니다.
입출력 예 #2
문자열이 남아있지만 짝지어 제거할 수 있는 문자열이 더 이상 존재하지 않기 때문에 0을 반환합니다.

나의 풀이

1차 풀이

function solution(s) {
    let string = s;
    const regExp = /([a-z])\1/;
    while (regExp.test(string)) {      
        string.replace(regExp, "")
        if (!string) return 1;
    }    
    return 0;
}

가장 먼저 생각났던 방법인 정규표현식과 while문, replace()를 이용해서 풀어봤는데 무한루프를 돌면서 시간초과로 실패하고 있다.

2차 풀이

function solution(s) {
    let string = s;
    const regExp = /([a-z])\1/g;
    while (regExp.test(string)) {      
        const newString = string.replaceAll(regExp, "");
        string = newString;
    };
    return string ? 0 : 1;
}

replaceAll 메서드는 새 문자열을 return 한다는 점이 떠올라서 string에 새 문자열을 할당하는 방식으로 풀이를 수정했다. 하지만 테스트 케이스 18문제 중 4문제가 시간 초과가 뜨면서 실패했다.

3차 풀이

function solution(s) {
    let array = s.split("");
    let answer = [];
    
    const isStringPairFound = () => {
        const regExp = /([a-z])\1/g;
        const stringPairExists = regExp.test(array.join(""))
        return stringPairExists
    }
    
    while (isStringPairFound()) {
        for (let i = 0; i < array.length; i++) {
            if (array[i] === array[i + 1]) {
                i++;
                continue;
            }
            
            if (!array[i]) break;
            answer.push(array[i]);
        }
        
        array = [...answer];
        answer = [];
    }

    return array.join("") ? 0 : 1;
}

stack을 사용해서 풀 수 있다는 힌트를 얻고 사용하는 메서드를 완전히 바꿔봤다. 하지만 stack과는 거리가 먼 풀이가 완성됐고, 여전히 replaceAll을 사용했던 지난 풀이와 비슷한 접근 방식이기 때문인지 시간 초과를 이유로 통과하지 못하고 있다.

while문을 없애야 할 거 같긴 한데 for문을 한 번 순회하고 나서도 짝지어 제거할 수 있는 문자열이 남았을 때 어떻게 처리해야 할지 다른 방법이 생각나지 않는다.

예를 들어 입출력 예 1번에서 for문 종료 후 'baabaa' -> 'bb'가 된다.

최종 풀이

function solution(s) {
    const stack = [];
    for (let i = 0; i < s.length; i++) {
        if (stack[stack.length - 1] === s[i]) {
            stack.pop();
        } else {
            stack.push(s[i]);
        }
    }
    return stack.length === 0 ? 1 : 0
}

다른 방법이 생각나지 않아서 다른 사람의 풀이를 참고해서 풀었다. 내가 생각해낸 풀이 방법은 아니지만 코드가 어떤 구조로 이루어져있는지 직접 손으로 풀어보며 완전하게 이해했기 때문에, stack의 구조와 구현 방법을 익힐 수 있는 좋은 기회였다고 생각한다.

빈 배열을 가지는 stack을 선언한다.
s의 길이만큼 for문을 돌면서 stack의 마지막 요소가 s[i]와 일치한다면 pop()을 이용해서stack의 마지막 요소를 제거한다.
stack의 마지막 요소가 s[i]와 일치하지 않는 경우에는 s[i]를 stack에 push()한다.
for문 실행 후 stack이 빈 배열이 된다면 짝지어 제거하기에 성공한 것이므로 stack의 length에 따라 최종값을 return한다.