728x90
반응형
짝지어 제거하기
❓ 문제설명
짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1, 아닐 경우 0을 리턴해주면 됩니다.
예를 들어, 문자열 S = baabaa 라면
b aa baa > bb aa > aa >
의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.
🚫 제한조건
문자열의 길이 : 1,000,000이하의 자연수
문자열은 모두 소문자로 이루어져 있습니다.
✔ 입출력 예
| s | result |
| baabaa | 1 |
| cdcd | 0 |
💡 풀이
function solution(s) {
const stack = []
// 최초 shift를 활용한 queue 형식으로 구현하였는데 시간초과
// 이 후 index를 통해 순회하는 방식으로 진행
for (let i = 0; i < s.length; i ++) {
const c = s.charAt(i)
if(stack[stack.length - 1] === c) {
stack.pop()
} else {
stack.push(c)
}
}
return stack.length > 0 ? 0 : 1
}📝 해설
문자열을 처음부터 읽으면서 직전 스택과 비교해서 같으면 pop, 다르면 현재 문자를 stack에 push하여 전체 문자열을 반복한 후 stack에 남은 문자가 있는지 확인하는 방식으로 해결.
스택과 큐를 사용하여 푸는 문제인데 배열에 shift 메서드를 사용하여 문자열을 배열로 split하여 queue 방식으로 문제를 풀었을 때 시간초과 이슈가 발생하여 문자열을 순회하였다. 앞으로도 queue를 사용해야할 때 대상 데이터가 문자열일 경우 index를 통해 순회하는 방식을 사용해야할 것 같다.
📚 참고자료
- Javascript 스택/큐 (추가예정)
728x90
반응형
