(풀어야함), 기말 문제 중복 문자 제거하기

B. 중복 문자 제거하기
- 탐욕적 알고리즘으로 해결하는 문제
 * 전수조사하기에는 경우의 수가 너무 많음
def solve(S, included, i, freq, done, ret):
    if i == len(S):
        ret.append(''.join(S[i] for i in range(len(S)) if included[i]))
        return    
    included[i] = False
    if S[i] in done: 
        solve(S, included, i+1, freq, done, ret)
    else:
        if freq[S[i]] > 1:
            freq[S[i]] -= 1
            solve(S, included, i+1, freq, done, ret)
            freq[S[i]] += 1
        included[i] = True    
        done.add(S[i])
        solve(S, included, i+1, freq, done, ret)
        done.remove(S[i])
  ** 결과 집합을 다시 정렬해야 함
 * 무조건 답에 만나는 문자를 추가
  ** 이때 답에 추가한 앞 문자들을 조사하여 현재 문자보다 뒤에 있는 문자인데 현재 문자 뒤에 해당 문자가 또 다시 등장하면 제거함
  ** 예) "bcabc"
  -> "b"
  -> "bc"
  -> "bca": b와 c가 모두 뒤에 등장하므로 제거
   >> 조사하는 가장 최근에 추가한 문자부터 (스택)
  -> "a" 

- 주어진 문자열의 빈도수 배열 구하기 freq
- 주어진 문자의 중복 제거가 완료되었는지 여부를 나타내는 불 배열 done 준비 (집합 자료구조 사용 가능)
 * 용량이 26인 배열로 충분하므로 집합 자료구조보다는 배열이 더 효과적임
- 스택 준비 (스택 대신 deque D를 사용하면 출력 처리가 편리함)
for c in S:
    freq[c] -= 1
    if not done[c]:
        while D and D[-1] > c and freq[D[-1]] > 0:
            done[D[-1]] = False
            D.pop()
        D.append(c)
        done[c] = True
 * 현재 문자를 살펴볼 때 스택에 저장된 문자를 살펴보면서 현재 문자보다 큰 문자이고 현재 문자 뒤에 해당 문자가 존재하면 스택에서 해당 문자를 제거함