1. 공부한 내용

문제1 - 99 클럽 - Remove K Digits:

[ 문제 풀이 ]

오늘의 문제는 숫자로 이뤄진 문자열이 주어졌을 때, k개의 숫자를 제거하여 만들 수 있는 숫자 중 가장 작은 값을 return하는 것이다. 나는 heapq를 사용하여 처음 시도하였고, 둘 째로 defaultdict와 deque을 사용하여 시도하였으나, 풀이 중간에 로직이 복잡해져 올바른 알고리즘이 아니라 판단하여 중도 포기하였다. 다른 사람의 풀이는 다음과 같았다.

풀이의 핵심은 새로운 숫자와 ans_str의 끝을 비교하여 ans_str의 값을 갱신하는 것이다.

1. 답으로 return할 stack을 선언한다.

2. 주어진 숫자 문자열을 하나씩 조회한다.

2-2) 3개의 기준이 모두 만족할 경우, stack의 마지막 값을 빼고, k -= 1로 갱신한다. 1) stack이 비어있지 않고, 2) k > 0, 3) stack[-1] > 현재 iteration에서 조회 된 숫자 일 경우

2-3)와 관계없이 stack에 다음 숫자를 무조건 append한다. ⇒ 다음 iteration에서 비교 후 갱신 결정됨

3. 만약 2) 과정에서 k가 0까지 줄어들지 않았다면, stack[:-k]를 최종 값으로 하고, 그렇지 않으면, 2)에서 결정된 stack을 최종 값으로 한다. (단, 0이 가장 좌측에 존재한다면, 모두 제외할 것)

[ Defaultdict 초기 값 ]

문제를 풀이하며 defaultdict를 여러번 마주하였으나 실제로 사용하고자 했던 시도는 이번이 처음이다. 초기 세팅이 헷갈려 찾아보니, 같이 할 수 있었다다.

⇒ 참고로 deque_dict = defaultdict(deque)도 가능하다.