[Leetcode] 316. Remove Duplicate Letters

문제 : https://leetcode.com/problems/remove-duplicate-letters/

---

문자열 s가 주어지면 모든 문자가 한 번만 나타나도록 중복되는 문자를 제거하라.

가능한 결과 문자열들 중 사전순으로 가장 작은 문자열을 구하라.

---

사전순으로 가장 작은 문자열을 구해야 하므로 앞에 있을수록 작은 문자열이 앞에 가야한다.

즉, 현재 만든 문자열에서 탐색 중인 문자를 추가하고자 할 때 정답 문자열에 있는 문자보다 탐색 중인 문자가 작다면 정답에 추가해주어야 한다. 이를 판단하기 위해 스택을 추가한다. 문자열 s를 앞에서부터 탐색하면서 스택에 정답 문자열을 만들 수 있는 문자들을 넣는다. 사전순으로 앞에 있는 문자열을 만들기 위해서는 앞으로 추가될 문자가 현재 정답문자열에 있는 문자보다 작다면 정답문자열에 있는 문자들을 제거한다.

예를 들어보자, s = "bcabc" 에서 스택에는 b, c가 차례대로 들어가고 a를 탐색할 차례라 하자. stack = [b, c]. a를 넣으려고 할 때 스택의 top에 있는 문자 c는 넣고자 하는 문자 a보다 사전순으로 크다. 따라서 c를 pop 해준다. (이 때, c가 모든 문자가 한 번만 나타나야 되는 조건을 만족하는지 체크해야 하지만 이는 뒤에서 별도로 언급하겠다.) 

이제 stack = [b]가 되고 다시 stack의 top에 있는 문자 b와 a를 비교해보면 마찬가지로 a가 사전순으로 앞서있으므로 b를 pop해준다. 

stack = []. 스택은 비어있으므로 a를 stack에 추가한다.

 

정답 문자열에는 중복되는 문자가 나타나면 안되므로 정답 문자열에 추가된 문자 체크를 위해 소문자 알파벳 갯수 크기만큼의 boolean 배열 check를 만든다. 만약 check[a] = true 라면 a문자가 정답문자열에 있다는 의미이다. 

예를 들어, s = "aba"일 때, 인덱스 2인 a를 탐색할 차례라 하자. stack = [a, b]가 있을것이고 check[a], check[b]는 true일 것이다. 현재 탐색하고 있는 문자가 'a'인데 이미 check[a]는 true이기 때문에 스택(정답 문자열)에 넣을 수 없고 다음 문자를 탐색하게 된다.

 

중복되는 문자는 제거하되 모든 문자가 한 번은 나타나야 하므로 정답 문자열을 만들기 전에 각 문자들의 등장횟수를 구한다. 이 int형 배열을 cnts라 하자. cnts[a] = 3, 이라면 문자열 s에서 문자 a가 3번 나타난다는 뜻이다. 정답 문자열을 만들어가며, 탐색한 문자의 cnts 요소를 1씩 감소시킬 것이다. 만일 탐색중인 문자와 스택에 있는 문자를 비교하여 스택에 있는 문자를 정답 문자열에서 제거하고자 할때, cnts[제거될 문자]가 0이라면 앞으로의 탐색에서 해당 문자가 나오지 않을 것이기 때문에 제거할 수 없다.

 

문자열 s를 탐색하면서 위 조건을 만족하며 스택을 모두 채웠다면 스택에서 문자들을 빼내면서 문자열을 만든다. 만든 문자열을 reverse 시키면 정답 문자열이 된다.

 

시간복잡도는 O(N).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/316.%20Remove%20Duplicate%20Letters.cpp

---

참고 : https://leetcode.com/problems/remove-duplicate-letters/discuss/1859410/JavaC%2B%2B-DETAILED-%2B-VISUALLY-EXPLAINED-!!