오늘의 문제는 주어진 문자열을 규칙에 맞게 재배열하여 사전순으로 가장 낮은 문자열을 구하여 return하는 것이다. 나는 초기에 문제를 잘못 이해하여, stack에 특정 idx까지 순서대로 문자열을 담는다면, 담긴 문자열은 한번에 빼야하는 것으로 이해했다. 이와 같은 규칙에 따라서는 알고리즘을 제대로 짰으나, 문제를 세밀하게 확인해보니 stack에 담긴 문자열을 한번에 모두 다 빼지 않아도 괜찮다는 것을 확인하였다. 이에 풀이를 수정하여 정답을 맞추었다.
나는 defaultdict, deque, stack을 활용하여 다음과 같이 풀이하였다.
defaultdict(deque)을 활용하여 각 문자열의 위치 index를 저장한다.
주어진 문자열의 unique한 알파벳의 순서를 확인한다. sorted(dict_s)
alpha_idx (sorted된 알파벳을 순서대로 접근하기 위함), start_idx (확인한 idx 뒤의 idx만 확인하기 위함), temp_stack = [] (문자열을 잠시 담아두기 위함), ans = “” 을 선언한다.
alpha_idx를 모두 다 훑을 수 있도록 반목문을 설정한다.
만약 dict_s[cur_alpha]가 남아 있지 않다면, 다음 alphabet을 가장 작은 alphabet을 취급하기 위해 alpha_idx += 1을 해주고, 만약 남아 있다면, 6)을 진행한다.
dict_s[cur_alpha]의 가장 좌측 idx를 end_idx로 취급한다. 이 end_idx가 start_idx보다 작다면, skip하고 만약 크거나 같다면, 7)을 진행한다.
만약 temp_stack이 비어있지 않다면, 현재 cur_alpha와 비교하여 이보다 작거나 같은 알파벳들을 모두 순서대로 pop하여, ans에 붙여준다.
7)이 종료되면, temp_stack에 다시 s[start_idx ~ end_idx바로 전]까지 추가해주고, start_idx = end_idx+1로 갱신, ans의 끝은 s[end_idx]를 붙여준다.
4)의 반복문이 종료되면, temp_stack이 비어있는지 확인하고, 만약 비어있지 않다면, ans에 남은 temp_stack을 역순으로 더해준다.
⇒ 다소 복잡하게 풀었으나, time complexity는 나쁘지 않았다.