[일간임무] - 짝지어 제거하기

figure 1a

Elapsed time : 60min

아니 문제 이해를 잘못했습니다. 예시에 주어진 'baabaa'가 사라지는 과정이, 먼저 연속된 요소인 'aa'을 찾고 'aa'와 일하는 문자가 입력값에 있으면 'aa'을 삭제한 나머지 'bbaa'를 통해서 다시 연속된 문자 'bb'와 일치하는 'bb'가 있을 때 지우며 푸는 것인줄 알았습니다.

그게 아니고 그냥 첫 번째 Index부터 연속되면 무조건 지우는 문제였습니다. 그래서 예시 'baabaa'가 사라지는 논리가 'b'다음에 'a'가 왔으니 연속된 문자가 아니라서 살려두고, 'ba'다음에 'a'가 와서 'aa'가 연속되었으니 'baa'에서 'aa'을 지운 'b'가 남는 것이었습니다. 이제 'b'와 나머지 'baa'을 비교하면 'b'와 'b'는 연속된 같은 문자이니 지워버리고 나머지 'aa'을 같은 논리로 풉니다.

요지는 이미 비교를 마친 문자 중에서 사라져야 할 것들이 있다는 것입니다. 'ba'까지 온 상태에서 다음 'a'가 이전 'ba'에서 'a'와 연속이기 때문에 'ba'에서 나중에 온 'a'을 없애야 합니다. stack을 바로 떠올린 건 아니지만 시도했던 방법 중엔 제일입니다.

'baabaa'에서 처음 Stack은 텅 비어 있을 것입니다. 아무것도 격납하지 않은 상태에서는 비교 자체가 안 되기 때문에 무조건 첫 번째 문자를 넣습니다. 그러면 stack에 'b'가 들어있을 것입니다. 

'baabaa'에서 첫 문자인 'b'가 stack에 있고 다음 for loop부터 'b'을 제외한 'aabaa'을 비교해나갈 것입니다. 'b'와 'a'는 연속된 글자가 아닙니다. 그래서 stack에 넣어서 'ba'을 만듭니다.

이미 검사한 문자 'ba'와 검사를 하지 않은 문자 'abaa' 중에서 'a'을 생각해봅시다. 'a'는 'ba'에서 'a'와 연속이기 때문에 사라져야 합니다. 그냥 stack에서 'a'을 제거해버리고 다음 문자 'b'을 검사하면 됩니다. 그러면 검사를 끝낸 문자는 'ba'에서 'b'가 될 것입니다. 같은 논리로 계속 전개하면 아마 될 것 같았는데 됩니다.