[Programmers / JS] 12973번 - 짝지어 제거하기

Problem

문제 보기

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

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

b aa baa → bb aa → aa →

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

제한사항
- 문자열의 길이 : 1,000,000이하의 자연수
- 문자열은 모두 소문자로 이루어져 있습니다.

---

Solution

function solution(s){
    s = s.split('');
    let i = 0;
    
    while (true) {
        if(s[i] === s[i+1]){
            s.splice(i, 2);
            i = 0;
        }
        else i++;
        
        if(s.length === 0) return 1;
        if(i === s.length) return 0;
    }
    
    return 1;
}

s의 i번째와 i+1번째 (i의 다음)이 같다면 splice로 제거해주고 i는 다시 0으로 리셋해줬다.
같지 않다면 i++로 그 다음 요소를 계속 확인해주도록 하였다.

그 결과

실패^^

정확성 테스트는 다 통과했다(물론 시간이 위 사진과 같이 오래 걸리는 게 있어서 아슬했다)
그러나 효율성 테스트에서 통과하지 못했다. 아마 splice로 요소를 제거해주면서 뒤에 있던 요소들이 다시 앞으로 당겨오는 반복으로 효율성에서 통과하지 못한 거 같다.

그렇다면 splice가 아니라 pop을 해줘야할 거 같다는 생각이 들었다.

---

function solution(s) {
    let copy = [];
    
    for(let i of s){
        copy.push(i);
        if(copy[copy.length - 1] === copy[copy.length - 2]){
            copy.pop();
            copy.pop();
        }
    }
    
    return copy.length === 0 ? 1 : 0;
}

pop을 사용하기 위해서는 새로운 배열을 하나 생성해주었다.
s의 앞에서부터 요소들을 copy에 넣어주고 copy의 마지막 요소와 마지막의 앞에 있는 요소랑 같다면 pop으로 제거해주도록 하였다.
그렇게 모든 s를 돌고나서 최종적으로 copy의 length가 0이라면 문자열을 모두 제거할 수 있으므로 1을 return하도록 하였고 아니라면 0을 return하게 했다.

테스트도 통과하고 이전 첫번째 코드보다 걸리는 시간도 단축되었다!