[Lv.2] 짝지어 제거하기
문제 설명
짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.
예를 들어, 문자열 S = baabaa 라면
b aa baa → bb aa → aa →
의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.
제한 사항
- 문자열의 길이 : 1,000,000이하의 자연수
- 문자열은 모두 소문자로 이루어져 있습니다.
풀이
먼저 나는 문제를 읽고 제한 사항을 중요시 본다.
제한 사항은 처음 문제 풀이의 방향을 잡는 데에 굉장히 중요한 역할을 한다.
제한 사항을 보면 매개변수로 받는 문자열의 길이가 최대 1,000,000이라고 했기 때문에 최악의 상황에서 반복을 돌렸을 때 1,000,000이 나와버린다.
따라서 이중 반복을 하게 되면 절대 풀 수 없는 문제가 되어버린다.
이때부터 이 문제는 한 반복으로 끝내야겠다는 생각을 하고 어떻게 풀지 설계를 한다.
- 문자열에서 같은 알파벳 2개 붙어있는 짝 찾기
- 2개 붙어있는 짝을 제거한 뒤 앞뒤로 문자열을 이어 붙임
- 반복해서 문자열이 모두 제거되면 1, 아니라면 0 반환
이렇게 단계별로 정리를 하고 다시 생각을 해본다.
가장 먼저 해야 할 것은 같은 알파벳 2개 붙어있는 짝을 찾고 제거를 해야 한다.
이것을 한 반복에 끝내기 위해서는 하나씩 순회하며 바로 2개가 되면 제거를 하는 과정이 필요하다.
그래서 나는 스택을 활용했다.
하나씩 순회하며 스택에 쌓고 2개가 되면 스택에서 바로 빼버리고 다시 쌓고를 반복하면
1, 2, 3단계가 한 번에 된다.
통과 코드
function solution(s) {
let stack = [];
for (let i = 0; i < s.length; i++) { // 문자열의 길이만큼 순회
stack.push(s[i]); // 스택에 넣기
if (stack[stack.length - 1] === stack[stack.length - 2]) { // 방금 스택에 넣은 것과 한 단계 전의 것이 같으면
stack.pop(); // 스택 맨 뒤에 요소 제거
stack.pop(); // 스택 맨 뒤에 요소 제거
// 두 번을 해주는 이유는 짝 2개를 모두 제거해야 하기 때문.
}
}
return stack.length ? 0 : 1; // 스택에 단 하나라도 문자열이 남아있다면 0, 빈 스택이면 1
}