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

문제 설명

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 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을 반환합니다.

 

풀이 - 1

처음엔 검증과정을 반복해야 할것 같아 while문을 사용하는 방법을 구상하였으나, 만족되지 않을경우를 걸러내기가 어려워 for문 안에서 짝지어진 문자를 제거하면 인덱스 값을 -2하는 식으로 구현해보았다.

문자열의 길이가 2이고 마지막 짝이 같다면 1, 아니라면 0을 리턴하도록 했다.

function solution(s) {
    // for문 - s문자열 길이만큼
    for (let i = 1; i < s.length; i++) {
        // if문 - 현재 인덱스와 이전 인덱스의 값을 비교
        if (s[i] === s[i - 1]) {
            // 같을경우 두 문자를 제거후 인덱스값을 지운만큼 빼준다.
            s = s.substring(0, i - 1) + s.substring(i + 1);
            i = i - 2;
        }
    }
    // 첫번째 요소와 두번째 요소를 비교하여 return
    return s[0] === s[1] ? 1 : 0;
}

시간복잡도는 for문 안에서 substring 함수를 사용하여 O(n^2)이며, 공간복잡도는 s문자열의 길이에 따라 O(n)이 되었다.

 

우선 주어진 테스트는 모두 통과 하였으나, 효율성 테스트를 한개를 제외하고 모두 틀리게 되었다.

 

풀이 - 2

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

풀이 - 1과 비교하였을때, 문자열을 그대로 다루기 보다 배열로 바꾸어서 사용하는 방법을 사용하는것이 시간복잡도상 이득이 되는것 같다.

시간복잡도와 공간복잡도 모두 O(n)이다.