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

# 문제 원문

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

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

b aa baa → bb aa → aa →

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

제한사항

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

---

입출력 예

s / result

baabaa	1
cdcd	0

# 문제 풀이

 

빅오O를 최대한 줄여야지 정답이 되는 문제. 처음에는 문자열이 가진 이터러블 속성을 이용해서 Set으로 char를 구해서 해당 char이 2개 이상이면서 짝수인것 들을 모두 split하고 join 하는 방식으로 접근했지만 단순 반복, 정규표현식, 모두 사용 해봐도 시간 초과가 떴다. 오히려 s만 순회하는 방식이 정확성에서는 시간 초과가 안뜬다는 것을 확인하고 단 한번만 문자열을 탐색하는 구조로 짜는 방향으로 접근 방법을 변경 했다.(이 문제을 통해서 split이나 Set이 내가 암묵적으로 생각하던 것보다 시간효율성이 높지 않다는 사실을 깨달았다.)

JS에서 문자열은 이터러블이니 Array.from으로 배열로 만들고 reduce 내장 함수의 result를 빈배열 스택으로 써서 스택과 current char를 비교하는 방식으로 문자열을 제거하여서 정답을 구했다.

 

# 솔루션 플로우

1. 입력 받은 문자열 s를 배열로 만들고 순회한다.

2. stack이 비어있거나 stack에 들어간 마지막 char이 현재 char과 다르다면 stack에 char을 push한다.

3. stack의 마지막 char과 current char이 동일하다면 stack을 pop한다.

4. 얻어진 result의 length가 1 이상일시 0을 0일시 1을 반환한다.

1. FP

function solution(s) {
    return Array.from(s)
        .reduce((result, current) => {
            if (result.length > 0 && result[result.length - 1] === current) {
                result.pop();
            } else {
                result.push(current);
            }
            return result;
        }, []).length > 0 ? 0 : 1;
}