LeetCode - The World's Leading Online Programming Learning Platform

문제 풀이 아이디어

스택: 순서를 유지하는 가운데 필터링을 해야할 때

해당 문제의 조건을 살펴보면 중복된 문자를 제거를 해야하지만 주어진 문자열에서 순서를 바꿔서는 안된다. 이렇게 순서를 유지해야 가운데 뭔가를 필터링 할 때는 Stack을 활용하는게 좋다. 필터의 대상이 되는 데이터들을 반복문을 돌리면서 Stack 안에 남겨둘 데이터는 push하고 제거할 데이터는 pop한다. 이 과정에서 stack의 남은 데이터의 선후관계는 유지되게 된다.

사전 상으로 빠른 문자를 최대한 앞으로

이 문제에서는 어떤 문자열의 중복된 문자는 제거한 결과물 중에 사전 순서대로 가장 앞에 오는 결과물을 리턴해야 한다. 따라서 각각의 문자를 순회하면서 사전 상으로 빠른 문자 (a → b → c → …)을 가장 앞으로 오도록 하면 된다.

이를 위해서 해당 문자보다 사전 상 뒤에 오는 문자가 stack.last에 있다면 자신보다 사전 상으로 빠른 문자가 stack.last가 될 때까지 stack.pop()을 해주면 된다. 다만 주의할 점은 만약 stack.last가 문자열에서 최소한 1개는 있어야 한다는 점이다.

이를 위해서 문자열에서 해당 문자가 몇개나 쓰이는지 세어둘 필요가 있다. 그리고 stack 안에 해당 문자열이 존재하는지 탐색을 하기 위해서 Array.contain을 쓸 수도 있지만 O(1)으로 접근하기 위해서 별로의 Set 자료형을 썼다.

나머지 설명은 코드의 주석으로 달아두었다.

코드

class Solution {
    func removeDuplicateLetters(_ s: String) -> String {
        // 반복문에서 사용이 용이하게 Array로 변경
        let chars = s.map { $0 }
        
        // s 안에서 각각의 char가 몇번씩 쓰였는지 체크
            // self로 그룹핑을 한 다음에 value를 count로 바꾸어주기
        var dict = Dictionary(grouping: chars, by: { $0 }).mapValues { $0.count }
        
        // 결과값을 저장할 stack
        var stack = [Character]()
        
        // 이미 쓰인 문자인지 확인할 set -> O(1)로 탐색하기 위해
        var check = Set<Character>()
        
        for char in chars {
            // 현재 char 뒤에 똑같은 char가 몇개 남아있는지 체크하기 위해서 현재 char의 갯수 -1
            dict[char, default: 0] -= 1
            
            // 만약이 stack에 넣은 char라면 continue (중복된 문자는 제거해야 하므로)
            if check.contains(char) {
                continue
            }
            
            // 현재 stack에 뒤에 있는 문자를 제거할 수 있는 조건 3가지
            while let toPop = stack.last, // 1. stack이 비어 있지 않음
                  char < toPop, // 2. char가 toPop 사전상으로 앞에 있는 글자
                  dict[toPop, default: 0] > 0 { // 3. 뒤에 있는 문자열에 현재 제거할 글자가 남아 있음 (= 뒤에 다시 넣으면 됨)
                check.remove(stack.popLast()!) // stack과 check에서 모두 제거
            } // -> while 문을 사용해서 해당 조건 만족하는 동안은 제거
            
            // 현재 char를 stack에 넣는다.
            stack.append(char)
            check.insert(char)
        }
        
        return stack.map { String($0) }.joined()
    }
}