Github

짝지어 제거하기

1. 개요

2. 문제 설명

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

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

b aa baa → bb aa → aa →

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

2-1. 문제 설명 - 제한사항

  • 문자열의 길이 : 1,000,000이하의 자연수

  • 문자열은 모두 소문자로 이루어져 있습니다.

2-2. 문제 설명 - 입출력 예

s
result

baabaa

1

cdcd

0

2-3. 문제 설명 - 입출력 예 설명

입출력 예 #1

위의 예시와 같습니다.

입출력 예 #2

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

3. 문제 풀이

function solution(s) {
  // 1) 스택으로 사용할 배열 만들기
  const string = [];
  for (let i = 0; i < s.length; i++) {
    // 2) 배열의 마지막 문자와 새롭게 추가될 문자가 같다면 배열의 마지막 문자 제거하기
    if (string[string.length - 1] === s[i]) string.pop();
    // 3) 그렇지 않다면 새롭게 추가될 문자를 배열에 추가하기
    else string.push(s[i]);
  }
  // 4) 배열의 길이에 따라 다른 값을 반환하기
  return string.length === 0 ? 1 : 0;
}

1) 스택으로 사용할 배열 만들기

const string = [];

아래의 반복문을 통해 string 배열에는 새로운 요소가 추가되거나 마지막 요소가 제거된다. 이는 후입선출의 구조이기 때문에 스택의 자료구를 가진다.

2) 배열의 마지막 문자와 새롭게 추가될 문자가 같다면 배열의 마지막 문자 제거하기

if (string[string.length - 1] === s[i]) string.pop();

string 배열의 마지막 문자(요소)와 새롭게 추가될 문자인 s[i]가 같다면 문제의 조건에 따라 둘다 제거가 되어야 하기 때문에 string 배열의 마지막 문자를 제거하고 새로운 문자도 추가하지 않는다.

3) 그렇지 않다면 새롭게 추가될 문자를 배열에 추가하기

else string.push(s[i]);

만약 그렇지 않다면 즉, string 배열의 마지막 문자와 s[i]가 다르다면 s[i]를 string 배열의 마지막 요소로 추가한다.

4) 배열의 길이에 따라 다른 값을 반환하기

return string.length === 0 ? 1 : 0;

string 배열이 0이라는 것은 모든 문자가 제거가 되었다는 것이므로 성공적으로 제거를 완료하였다. 그렇기 때문에 문제의 조건에 따라 1를 반환하고 그렇지 않으면 0를 반환한다.

결과

4. Conclusion

처음으로 해당 문제를 풀었을 땐 스택 자료구조 아니라 계속 반복문을 돌면서 앞 뒤 문자를 비교하였다. 해당 방법으로 구현을 하니 테스트 케이스는 통과를 하였지만 제출한 코드에서는 시간초과가 발생하였다. 즉, 효율적인 자료구조가 필요하는 것이었다. 그래서 다음으로 생각한 풀이가 바로 위의 풀이이다. 스택 자료구조는 비교적 구현이 쉬워 빠르게 코드 작성이 가능해서 오랜 시간이 걸리 않았지만 아쉬운 점은 이 문제를 처음으로 보고 스택으로 풀어야겠다. 라는 것을 생각하지 못햇다는 것이다. 문제 자체는 쉬워 Level2이 아니라 Level1로 느껴졌다. 제한사항을 잘 보면서 한 번에 효율적인 풀이를 떠오를 수 있는 연습을 많이 하자.

📅 2022-09-27

Previous캐시Next구명보트

Last updated