[Programmers] 짝지어 제거하기
문자열 중 똑같은 단어가 두번 반복되면 제거하고, 이 과정을 반복하는 문제이다.
예를들어 baabaa가 있다면 baabaa -> bbaa -> aa -> 없음
과 같이 문자열이 완전히 지워지면 1을, 안지워진다면 0을 반환하는 문제이다.
문제풀이 전략
처음에는 투포인트를 활용하여 풀려고 했다.
하지만 투포인트를 사용하기 위해서는 만약 문자가 같은 경우 지워진 후 이전 문자를 가리키기 위해 탐색을 해야한다. 이 과정을 하기 위해 이전 위치를 저장하거나 반복문을 통해 탐색하여야 하는데, 시간초과가 걸리게 된다.
따라서 stack을 사용하여 문제를 풀어 보았다.
한 글자 씩 스택에 집어 넣으면서 스택의 top과 현재 가리키고 있는 문자가 같으면 스택을 pop 한 후, 다음 문자를 가리키도록 한다.
반면 문자가 다른 경우 현재 가리키는 문자를 스택에 push 한 후 다음 문자를 가리키도록 한다.
만약 가리키는 문자가 문자열의 끝 이후 일 때 스택이 비어있다면 다 지워졌다는 의미이므로 1을 반환하고, 아니라면 지워지지 않은 것이므로 0을 반환하도록 한다.
코드
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int solution(string s)
{
int answer = -1;
stack<char> st;
st.push(s[0]);
int idx = 1;
while(1){
if(!st.empty() && st.top() == s[idx]){
st.pop();
idx++;
}else{
st.push(s[idx]);
idx++;
}
if(idx >= s.size()){
if(st.empty()){
answer = 1;
}else
answer = 0;
break;
}
}
return answer;
}
출처 : 프로그래머스
https://programmers.co.kr/learn/courses/30/lessons/12973
Author And Source
이 문제에 관하여([Programmers] 짝지어 제거하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kms9887/Programmers-짝지어-제거하기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)