💻출처 : 프로그래머스 > 코딩 테스트 연습 > 2017 팁스타운 > 짝지어 제거하기
🏆난이도 : Level 2
📜 문제
📝 요약
알파벳 소문자로 이루어진 문자열이 주어진다. 문자열에서 같은 알파벳이 붙어있다면, 그 둘을 제거한 뒤 앞뒤를 이어붙인다. 이 과정을 반복하여, 더이상 문자열을 제거할 수 없을 때 문자열이 남아있지 않은 상황이라면 1을, 문자열이 남아 있다면 0을 반환한다.
🧠 문제 분석
현재, 주어질 수 있는 문자열의 최대 길이는 1,000,000이다.
따라서 직접 같은 알파벳이 두개가 붙어있는 부분을 찾고, 해당 부분을 지운 뒤 다시 처음부터 탐색하여 다시 동일한 알파벳 두개가 붙어있는 부분을 찾는 방식은 시간초과가 날 것이라고 생각하였다.
문자열을 지울 지의 여부는 현재 관찰하고 있는 문자의 앞뒤만 보고도 판단할 수 있다. 예컨데 abbcc 문자열에서 2번째 인덱스인 b를 관찰한다고 하였을 때, 2번째 인덱스에 인접한 인덱스, 즉, 인덱스 1번과 인덱스 3번만 관찰하면 된다.
또한, 짝지어진 알파벳을 제거한 후, 남은 문자열의 앞뒤를 이어붙여야 하기 때문에, 짝지어진 알파벳 이외에도 나머지 알파벳들을 알고 있어야 한다.
💡 풀이 방법
위의 분석을 통해, 이 문제에 가장 적합한 자료구조는 stack이라고 판단하였다.
stack을 이용한다면, 현재 조회하는 문자와 인접한 문자를 stack의 top에서 쉽게 확인할 수 있으며, pop연산을 통해 문자 제거 및 이전 문자열과의 연결을 쉽게 구현할 수 있기 때문이다.
구체적인 구현방식은 아래와 같다.
- 문자열을 맨 앞에서 부터 한 문자씩 순서대로 조회를 한다.
- 현재 조회한 문자가
stack의top에 있는 문자와 동일하다면,stack에서pop을 수행한다. (짝지어졌으므로 제거) - 만약 현재 조회한 문자가
stack의top에 있는 문자와 다르다면stack에 저장한다. - 문자열을 끝까지 조회한 뒤,
stack에 문자가 남아있다면 0을 반환하고,stack에 문자가 남아있지 않다면 1을 반환한다.stack문자가 남아있다는 것은, 제거되지 않은 문자들이 있다는 것을 의미하기 때문이다.
💻 코드
위의 풀이과정을 코드로 구현하였다.
stack에 아무 것도 없는 경우는 조회할 top이 없기 때문에, 바로 조회한 문자를 push해주었다.
function solution(s)
{
const length = s.length
const stack =[]
for(let i = 0; i<length;i++){
if(stack.length === 0)
stack.push(s[i])
else
stack[stack.length-1] === s[i] ? stack.pop() : stack.push(s[i])
}🎤 느낀 점
stack을 떠올릴 수 있었다면 구현은 쉬웠던 문제라고 생각한다!
좀 더 어려운 응용 문제를 풀기 위해, 어떤 상황에서 stack을 사용하면 되는지를 위주로 정리해보았던 문제였다 :)
