2022.02.21(Mon.)<프로그래머스 짝지어 제거하기 문제 풀이>

1. 문제 설명

코딩테스트 연습 - 짝지어 제거하기

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

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

b aa baa → bb aa → aa →

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

 

2. 제한 사항

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

 

3. 입출력 예제

s	result
baabaa	1
cdcd	0

 

4. 나의 접근 방식

• 처음에는 split으로 모든 문자를 나누어 보았다.
• 이후, 가장 처음 문자를 보고 두번째 문자와 비교해서 같으면 shift 두 번으로 빼버리려고 했다. 완전히 실패.

실패한 코드

function solution(s) {
    let splitStr = s.split('');

    for(let i = 0; i < splitStr.length; i++) {
        let first = splitStr[i];
        if(first === splitStr[i + 1]) {
            splitStr.shift();
            splitStr.shift();
        }
        else {
            // 맞지 않으면 다시 뒤로 넣어준다.
            splitStr.push(first);
        }
    }
    
    // 한번 이상 검사할 수 없기 때문에 무조건 0이 나온다.
    if(splitStr.length === 0) return 1;
    else return 0;
}​

• 그런대 잘 생각해 보니 앞에서부터 할 필요가 없이, 스택처럼 쌓아서 뒤부터 보고 연속으로 같은 문자가 들어오면 뒤를 빼버리면 될 것이라고 생각했다.

 

4. 결과

function solution(s) {
    // 스텍으로 쓸 빈 배열을 만든다.
    let arr = [];
    
    for(let i = 0; i < s.length; i++) {
        // 각 요소들을 넣어주면서
        arr.push(s[i]);
        // 뒤부터 들어온 스텍에 똑같은 문자가 연속해서 들어 온다면,
        if(arr[arr.length - 1] === arr[arr.length - 2]) {
            // 두개를 빼 버린다.
            arr.pop();
            arr.pop();
        }
    }
    
    // 반복문을 다 돌고 나서, 스텍이 비어 있다면 전부 제거가 된 것이다.
    if(arr.length === 0) return 1;
    // 만약, 겹치지 않았다면 스텍에는 요소가 남아 있을 것이므로, 0을 반환한다.
    else return 0;
}

 

5. 개선점이 있다면?

• 위의 방법으로도 왠지 풀 수 있을 것 같다...! (물론, 쉽지도 않고 효율도 떨어질 것이다)
• 다양한 방식의 문제를 접하고, 어떻게 풀어야 할 지 더 다양한 방법으로 생각하는 것이 중요할 것 같다.
• 조금 실수가 있었었다. 위의 문제는 split을 쓰면 올바르게 답을 작성해도 시간 초과가 나와서 테스트를 실패한다. 굳이, split을 쓰지 않고, 문자열 상태 그대로 반복문으로 해결할 수 있는 부분인데, pop과 같은 배열에서 사용할 수 있는 함수를 사용하려고 바꿨던 것이다. 이런 식으로 필요 없는 함수의 사용을 줄여 효율성을 생각하는 것도 중요한 부분이 될 것이다.