Stack 유형 - 문자열

 

문자열 문제

스택을 사용하는 문자열 문제는 자주 나옵니다. 

일반적인 문자열 문제는 문자열을 순회하면서, 문자를 스택에 넣고, 각 반복에서 현재 문자와 스택의 맨 위 문자를 비교하는 것이 있습니다. 스택은 가장 마지막 문자를 가지고 있기 때문에 문자열 매칭에 유용합니다.

 

 

예제 1

• 주어진 문자열 s는 (, ), {, }, [, ] 만 포함합니다.
• 입력 문자열이 유효한지 판단하세요.
• 문자열이 유효하려면 모든 여는 괄호가 동일한 유형의 닫는 괄호에 의해 올바른 순서로 닫혀야 하며, 각 닫는 괄호는 정확히 하나의 여는 괄호를 닫아야 합니다.
• 예를 들어, s = ( { } ) 는 유효하지만, s = ( ] 는 유효하지 않습니다.

 

방법

올바른 순서는 이전의 여는 괄호가 무엇이었는지에 의해 결정됩니다. 닫는 괄호가 나타날 때마다 가장 최근의 여는 괄호와 대응해야 합니다. 예를 들어, 문자열이 ( { [ 로 시작하고, 다음 3개의 문자가 닫는 괄호라면, 여는 괄호가 등장하는 순서대로 ] } ) 여야 유효합니다. 순서는 LIFO입니다. 마지막으로 본 여는 괄호가 첫 번째로 닫혀야 합니다.

 

문자열을 순회하면서 여는 괄호를 보면 스택에 넣습니다. 닫는 괄호를 보면, 스택의 맨 위에서 가장 최근에 닫히지 않은 여는 괄호를 확인합니다. 일치하면 계속 진행하고, 일치하지 않거나 스택에 여는 괄호가 전혀 없는 경우에는 문자열이 유효하지 않음을 알 수 있습니다. 마지막에는 매치되지 않은 여는 괄호가 없어야 하므로, 문자열이 유효하려면 스택이 비어 있어야 합니다.

 

여는 괄호와 닫는 괄호는 어떻게 연결할 수 있을까요? 각 여는 괄호를 닫는 괄호에 매핑하기 위해 해시 맵을 사용할 수 있습니다. 그러면 닫는 괄호를 볼 때, 스택의 맨 위를 key로 사용하여 값이 현재 문자와 일치하는지 확인할 수 있습니다.

 

 

정리

• 문자열을 순회하며 여는 괄호는 스택에 넣고 닫는 괄호는 스택에서 가장 마지막으로 넣었던 여는 괄호와 비교합니다.
• 올바른 순서로 닫히는지 확인하기 위해 해시 맵을 사용하여 여는 괄호와 닫는 괄호를 매핑합니다.
• 문자열 순회가 끝난 후 스택이 비어 있어야 문자열이 유효합니다.

class Solution {
    func isValid(_ s: String) -> Bool {
        // 스택 생성
        var stack: [Character] = []
        
        // 해시맵을 이용하여 각 괄호의 짝지를 정의
        let matching: [Character: Character] = ["(": ")", "[": "]", "{": "}"]
        
        // 문자열 순회
        for c in s {
            // keys 중 동일한 문자열이 있는지 체크
            if matching.keys.contains(c) { 
                stack.append(c)
            } else {
                // 저장된 여는 괄호가 없는데, 닫힌 괄호가 들어왔다면 문자열이 유효하지 않음
                if stack.isEmpty {
                    return false
                }
                
                // 마지막으로 저장된 요소를 pop
                let previousOpening = stack.removeLast()
                
                // 가장 최근에 저장된 요소와 닫는 괄호가 매칭이 되는지 체크
                if matching[previousOpening] != c {
                    return false
                }
            }
        }
        
        return stack.isEmpty
    }
}

 

각 요소는 한 번만 push되거나 pop될 수 있고, 이 연산은 O(1)이기 때문에 알고리즘의 시간 복잡도는 O(n)입니다.

스택의 크기가 입력 크기에 따라 선형적으로 증가할 수 있기 때문에 공간복잡도는 O(n)입니다.

 

이 문제의 핵심은 문제가 LIFO 성격을 가지고 있다는 것을 인식하는 것입니다. "최근의 여는 괄호가 첫 번째로 닫혀야 한다!!"

 

 

예제 2

• 영어 소문자로 구성된 문자열 s가 주어집니다.
• 인접한 중복 문자를 계속해서 제거하여 더 이상 제거할 수 없을 때까지 반복합니다.
• 최종 문자열을 반환하세요.

 

예시 1

• s = "abbaca"
• 정답: ca
• abbaca에서 문자가 인접하고 같으므로 bb를 제거할 수 있습니다. 
• 이 결과 문자열은 aaca고, 이 중 aa만 가능하기 때문에 최종 문자열은 ca임

 

예시 2

• s = "azxxzy"
• 정답: ay

 

방법

이 문제의 까다로운 부분은 모든 제거가 처음부터 가능한 것이 아니라는 점입니다. 예시에서 볼 수 있듯이, aa를 삭제하려면먼저 bb를 삭제해야 가능합니다. 첫 번째 문자는 많이 지난 후에 제거할 수 있습니다.

 

입력이 s = "abccba" 라면 b에서도 동일한 문제가 발생하며, a는 그 뒷 단계에 있습니다. 삭제 순서는 c -> b -> a 입니다.

입력을 순회하며, 문자를 스택에 넣습니다. 각 단계에서 스택의 맨위가 현재 문자와 같다면, 그들은 인접해 있으며 삭제할 수 있습니다.

 

정리

• 주어진 문자열을 순회하면서 문자를 스택에 넣습니다.
• 각 단계에서 스택의 맨 위 문자와 현재의 문자와 같다면, 인접한 중복 문자이므로 스택에서 제거합니다.
• 최종적으로 스택에 남은 문자들을 합쳐서 최종 문자열을 반환합니다.

class Solution {
    func removeDuplicates(_ s: String) -> String {
        var stack: [Character] = []

        for c in s {
            let lastElement = stack.last

            // 마지막 요소와 현재 요소가 일치하는지
            if lastElement == c {
                stack.removeLast()
            } else {
                stack.append(c)
            }
        }

        return String(stack)
    }
}

 

시간 복잡도와 공간 복잡도는 모두 O(n)입니다.

 

 

예제 3

• 문자열 s와 t가 주어집니다. 빈 텍스트 편집기에 두 문자열을 입력했을 때, 둘이 같으면 참을 반환합니다.
• #은 백스페이스 문자를 의미합니다.
• 빈 텍스트에 백스페이스를 입력한 후에는 텍스트가 계속 비어 있습니다.

 

예시 1

• s = "ab#c", t = "ad#c"
• 정답: true
• s와 t는 모두 ac가 됩니다.

 

예시 2

• s = "ab##", t = "c#d#"
• 정답: true
• s와 t는 모두 ""가 됩니다.

 

예시 3

• s = "a#c", t = "b"
• 정답: false
• s는 "c",  t는 "b"가 됩니다.

 

방법

백스페이스는 후입선출 패턴을 따르므로, 첫 번째로 삭제되는 문자는 가장 최근에 입력된 문자입니다. 스택을 사용하여 문자열 입력을 시뮬레이션하고, 마지막에 비교할 수 있습니다.

 

문자를 입력할 때는 스택에 push합니다. 스택의 맨 위에 있는 문자는 가장 최근에 입력된 문자이므로 백스페이스 시에는 pop을 하면 됩니다. 빈 문자열에서 백스페이스하는 경우의 케이스에 주의하세요.

class Solution {
    func backspaceCompare(_ s: String, _ t: String) -> Bool {
        var sStack: [Character] = []
        var tStack: [Character] = []

        for c in s {
            // 백스페이스 마지막 요소 제거
            if c == "#" {
                sStack.popLast()  // 마지막 요소가 없을 경우 에러를 반환하지 않음
            } else {
                sStack.append(c)
            }
        }

        for c in t {
            // 백스페이스 마지막 요소 제거
            if c == "#" {
                tStack.popLast()
            } else {
                tStack.append(c)
            }
        }

        return String(sStack) == String(tStack)
    }
}

중첩 함수 사용

class Solution {
    func backspaceCompare(_ s: String, _ t: String) -> Bool {
        func bulid(c: String) -> String {
            var cStack: [Character] = []

            for i in c {
                // 백스페이스 마지막 요소 제거
                if i == "#" {
                    cStack.popLast()
                } else {
                    cStack.append(i)
                }
            }

            return String(cStack)
        }
        
        return bulid(c: s) == bulid(c: t)
    }
}

 

이전 접근 방식들과 마찬가지로, 입력 크기에 따라 선형적인 시간 및 공간 복잡도를 가집니다.

 

스택을 사용하여 다른 문제들도 직접 해결해보세용~

 

 

 

 

 

Reference:

https://leetcode.com/