달랩 코딩 도장 8번째 회고

짝지어 제거하기

문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾아서 모두 제거할 수 있는지 확인하는 함수를 작성하는 문제를 풀었다. 먼저 문제를 이해하면서 원하는 것을 정의하고 계획하고 문제를 풀었다. 대충 이런 식으로 가짜 코드를 작성했다.

같은 알파벳이 2개 붙어 있는 문자열을 찾는다.
if 찾았다
  그 알파벳을 제거한다.
  if 남은 알파벳의 길이가 0이다.
    return 1
  else 
    처음으로 다시 돌아간다.
if 못 찾았다.
  return 0

계획을 작성할 때 계속 같은 알파벳 2개를 어떻게 판단할 수 있을까에 빠져서 일단 세부 구현은 나중에 신경 쓰기로 하고 큰 계획을 작성했다. 그 다음에 알파벳 2개를 찾는 것을 다시 이해를 하고 계획하고 하여 여러 방법이 나왔다. 정규식을 이용하는 방법, for loop를 이용하는 방법등이 나왔다. 일단은 for loop를 돌도록 문제를 풀기로 하고 문제를 풀었다.

먼저 작은 문제부터 시작하기로 하여 문자열이 2개일 때, 3개일 때, 4개 일 때로 문제를 풀었다. 처음에 재귀로 문제를 풀었는데 효율성에서 통과하지 못하여 재귀 대신에 while을 써서 문제를 해결하고 그래도 안돼서 다시 정규식을 이용해서 문제를 풀어도 효율성을 통과하지 못했다. 중복되는 작업이 어디서 일어나는지 파악해보니, 짝을 제거하고 나면 다시 짝이 생기는데 이 작업에서 같은 일을 반복하는 작업을 찾아냈다. 어떻게 하면 이 작업을 없앨 수 있을까, 한 번에 문제를 해결할 수 있는 방법이 없을까 해서 앞에서부터 없애나갈려다보니 stack 자료구조를 이용했고 문제를 해결했다.

좋았던 점

• 중복되는 작업을 찾아서 제거하여 효율성을 높이는 연습을 해서 좋았다.

Sources

• https://programmers.co.kr/learn/courses/30/lessons/12973
• https://github.com/dal-lab/coding-dojo/pull/66/