프로그래머스 코딩테스트 연습 Level 2 - 짝지어 제거하기 (JavaScript)

프로그래머스 코딩테스트 연습 Level 2 - 짝지어 제거하기 (JavaScript)

 

 

Programmers(프로그래머스)의 코딩테스트 연습문제 Level 2 중,

[짝지어 제거하기] 문제를 JavaScript를 사용하여 해결해 보도록 하겠습니다.

 

문제

문제 설명

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

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

b aa baa → bb aa → aa →

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

 

제한사항

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

 

입출력 예

s	result
baabaa	1
cdcd	0

 

입출력 예 설명

입출력 예 #1
위의 예시와 같습니다.

 

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

※ 공지 - 2020년 6월 8일 테스트케이스가 추가되었습니다.

 

 

작성한 답

solution.js

function solution(s) {
    const stack = [];
    for (const c of s) {
        if (stack[stack.length - 1] === c) stack.pop();
        else stack.push(c);
    }
    return stack.length > 0 ? 0 : 1;
}

 

설명

처음에는 정말 간단한 문제인줄 알고 만만하게 보고 했지만 효율성 테스트에서 시간 초과로 3번째 방식으로 변경하고나서야 성공한 문제였습니다.

 

제가 실패한 방식들을 먼저 보여드리자면,

첫번째 실패한 방식

function solution(s) {
    const arr = s.split("");

    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] === arr[i + 1]) {
            arr.splice(i, 2);
            i = -1;
        }
    }
    return arr.length === 0 ? 1 : 0;
}

문제의 예시처럼 정말 순수하게 앞에서부터 같은 2개의 문자가 나오면 지우고 다시 처음부터 같은 문자 2개 나오는 것을 확인하는 방식으로 구현하였습니다. 생각해보면 당연히 효율성이 너무도 좋지 않은 방식인데 이 방식을 가장 먼저 구현했던 저는 아직 많이 부족하다는 생각까지 듭니다.

 

두번째 실패한 방식

function solution(s) {
    while (s.length !== 0) {
        const newString = s.replace(/(\w)\1/g, '');
        if (newString === s) return 0;
        s = newString;
    }
    return 1;
}

문자열을 다루는 문제에서 정규식만한게 없다고 보통 생각했기에 정규식을 사용하여 같은 문자 2개가 연속되는 것을 지워나가는 방식으로 구현했습니다. 하지만 이 방식마저도 효율성에서 실패했습니다. 지금 다시 생각해보면 이 방식 역시 정말 많은 문자열과 복잡한 구조에서는 반복 횟수가 많아질 수 밖에 없는 구조였습니다.

 

 

그리하여 마지막으로 성공한 방식을 설명드리자면 스택을 사용한 방식으로 이 방식을 사용하면 딱 문자열 길이만큼만 반복하여 문제를 해결할 수 있습니다.

문자열의 처음부터 한 문자씩 반복문을 시작하여 스택의 마지막이 현재의 문자와 같은 문자면 스택에서 해당 문자를 제거하고, 다른 문자라면 스택에 넣는 것으로 같은 문자가 2번 들어오는 순간마다 문자를 바로바로 제거할 수 있습니다.

이러한 관련 문제가 상당히 많이 있는데 먼저 이러한 방식을 떠올릴 수 있도록 더 노력해야겠습니다.

 

또한 문제를 해결하면서 한가지 알게된 사실은 스택으로 사용중인 배열의 마지막을 구하기 위해 Array.at() 메소드를 사용했었는데 이 메소드를 사용하면 효율성에서 실패하게 됩니다. 내부 방식까지는 파악하지 못했으나 Array[Array.length - 1] 를 사용하는 것이 속도가 더 빠르다는 것을 알게 되었습니다.

 

 

 

도움이 되셨다면 공감, 댓글 부탁드립니다!

궁금하신 점이나 요청사항은 언제든지 말씀해주세요!

피드백도 언제나 환영입니다!

 

감사합니다.