[Leetcode/Medium] 중복 문자 제거 (316. Remove Duplicate Letters, Swift)

https://leetcode.com/problems/remove-duplicate-letters/description/

 

🤔 문제 설명

문자열이 주어지면 모든 문자가 "한 번"만 나타나도록 중복된 문자를 제거한 후,
"만들어지는" 모든 문자열 중에서 결과가 사전 순서 (Lexicographical order)에서 가장 작은 것인지 확인하라.

*사전 순서 (Lexicographical order)의 의미 : a는 b보다 사전적으로 작다. + 문자 "ab"와 "abc"가 있다면 "ab"가 사전적으로 더 작다.

s = "bcabc"
// "abc"

s = "cbacdcbc"
// "acdb" 
// 중복된 문자를 제거한 "abcd"를 사전 순으로 재정렬하라는 의미가 아님.
// 주어지는 문자열의 순서는 유지되는 상황에서 중복을 제거하라는 의미.

 

💡 풀이

스택(Stack)을 사용해서 문제를 해결했다.

기본 원리는 주어진 문자열에서 문자를 하나씩 반복(current)하면서 스택에 담겨있는 가장 상위의 값(top)과 비교해 current가 더 크면 스택에 push, 더 작으면 top을 pop 하는 반복을 수행하는 것이다.

이때 추가로 생각해준 예외 조건이 몇 가지 있다.

• 중복을 제거하는 것이지, 처음 주어진 문자열에 존재하는 문자가 하나라도 있으면 그 문자는 반드시 포함되어야 한다. -> 예제 "cbacdcbc"에서 d 다음 c가 반복되는데, 이때 d를 제거할 수 없다는 의미! (이후에 d가 한 번도 나오지 않으니 d가 pop 되면 사용할 수가 없다.)
• 기존 스택에 반복하려는 현재 문자와 동일한 문자가 있으면 push할 수 없어야 한다. (중복 체크) 

특히, 위에서 첫번째 예외 조건을 처리해 주기 위해 나는 문자열(s)을 배열(sArray)에 저장해 두고, 배열에서 하나씩 빼가면서 반복을 돌리는 방식을 선택했다.
이 방식에서 이후에 해당 문자가 나올 수 있는지를 체크할 때, 배열에 해당 문자가 있는지 (= 이후에 빼갈 문자가 있는지)를 확인해 줬다.

 

🧑🏻‍💻 코드 (Swift ver.)

💡 Runtime : 1089ms (Beats 45.45%), Memory : 36.36MB (Beats 73.72%)

class Solution {
    func removeDuplicateLetters(_ s: String) -> String {
        var sArray = s.map { $0 }   // s 문자열을 배열에서 시작
        var stack = [Character]()   // 사전순을 체크할 스택

        while (!sArray.isEmpty) {
            var current = sArray[sArray.startIndex...].popFirst()
            var top: Character? = stack.last

            while let topValue = top, topValue >= current!, !stack.contains(current!) {
                if (!sArray.contains(topValue)) { break }   // top을 빼도 상관이 없는지 확인
                stack.popLast()
                top = stack.last
            }

            // 스택에 해당 문자가 있는지 확인 (= 중복 체크)
            if (!stack.contains(current!)) { stack.append(current!) }
        }

        return String(stack)
    }
}