문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾아서 모두 제거할 수 있는지 확인하는 함수를 작성하는 문제를 풀었다. 먼저 문제를 이해하면서 원하는 것을 정의하고 계획하고 문제를 풀었다. 대충 이런 식으로 가짜 코드를 작성했다.
같은 알파벳이 2개 붙어 있는 문자열을 찾는다.
if 찾았다
그 알파벳을 제거한다.
if 남은 알파벳의 길이가 0이다.
return 1
else
처음으로 다시 돌아간다.
if 못 찾았다.
return 0
계획을 작성할 때 계속 같은 알파벳 2개를 어떻게 판단할 수 있을까에 빠져서 일단 세부 구현은 나중에 신경 쓰기로 하고 큰 계획을 작성했다. 그 다음에 알파벳 2개를 찾는 것을 다시 이해를 하고 계획하고 하여 여러 방법이 나왔다. 정규식을 이용하는 방법, for loop를 이용하는 방법등이 나왔다. 일단은 for loop를 돌도록 문제를 풀기로 하고 문제를 풀었다.
먼저 작은 문제부터 시작하기로 하여 문자열이 2개일 때, 3개일 때, 4개 일 때로 문제를 풀었다. 처음에 재귀로 문제를 풀었는데 효율성에서 통과하지 못하여 재귀 대신에 while을 써서 문제를 해결하고 그래도 안돼서 다시 정규식을 이용해서 문제를 풀어도 효율성을 통과하지 못했다. 중복되는 작업이 어디서 일어나는지 파악해보니, 짝을 제거하고 나면 다시 짝이 생기는데 이 작업에서 같은 일을 반복하는 작업을 찾아냈다. 어떻게 하면 이 작업을 없앨 수 있을까, 한 번에 문제를 해결할 수 있는 방법이 없을까 해서 앞에서부터 없애나갈려다보니 stack 자료구조를 이용했고 문제를 해결했다.
자바스크립트로 직접 만들면서 배우는 - 자료구조와 알고리즘 강의 바로 가기
기계인간 이종립, 소프트웨어 개발의 지혜 - Git 강의 바로 가기
코드숨에서 매주 스터디를 진행하고 있습니다. 메일을 등록하시면 새로운 스터디가 시작될 때 알려드릴게요!