Swift) LeetCode(Easy) - Backspace String Compare (TwoPointer & Stack)

안녕하세요 후르륵짭짭 입니다.

이번에는 스택 또는 투포인터를 활용해서 풀 수 있는 문제를 준비했습니다.

leetcode.com/problems/backspace-string-compare/

Backspace String Compare - LeetCode

 

** 문제 해설 **

두개의 문자열 S와 T가 주어졌을 때, 각각의 문자열에서 # 된 문자열 앞에 것은 지웠을 때, 두 문자열이 같은지 확인하는 문제 입니다.

S = a# 이고 T = b# 일 때, 둘다 ""이라서 결과는 true 이죠 ㅎㅎㅎ

 

** 스택을 활용한 풀이  **

스택으로 풀었을 때는 , 간단하게 두 문자열을 모두 String 배열로 바꿔 줍니다. 

그리고 두 문자열의 변화 된 값을 담을  String 타입 배열 두개를 준비합니다.

그리고 check 함수를 통해서 넣어주고 빼줍니다.

  func backspaceCompare(_ S: String, _ T: String) -> Bool {
        
        let arrayS = Array(S)
        let arrayT = Array(T)
        
        var listS : [String] = []
        var listT : [String] = []
        
        for element in arrayS{
            check( String(element) , &listS)
        }
        
        for element in arrayT{
            check( String(element) , &listT)
        }
        
        let tempS = listS.reduce("", +)
        let tempT = listT.reduce("", +)
            
        return tempS == tempT ? true : false
        
    }
    
    private func check(_ char : String , _ list : inout [String]){
        
        if char == "#"{
            if list.isEmpty == false{
            list.removeLast()
            }
            return
        }
            
        list.append(char)
    }
    

(참고로 reduce 함수는 (초기값 , 수행 방법) 으로 구성 되어 있습니다.

answer.reduce("") { (str1, str2) -> Int in
            return number1 + number2
        }

 

str1은 초기값의 결과 str2는 그 다음 값 이 됩니다.

그래서 이런식으로도 구현이 가능합니다. 

)

 

** TwoPointer **

m.blog.naver.com/kks227/220795165570

투 포인터(Two Pointers Algorithm), 슬라이딩 윈도우(Sliding Window) (수정: 2019-09-09)

투포인터 알고리즘은 간단하게 두개의 변수를 이용해서 푸는 알고리즘을 투포인터 알고리즘이라고 합니다.

투 포인터 알고리즘 같은 경우는

1) 시간을 O(n)으로 풀이가 가능해야하고

2) 공간복잡도(1)으로 변화가 없어야 합니다.

이런 조건을 생각하고 풀어야하는 것입니다..... (사실 전 이런 분야에 약합니다 매우)

    func twoPointer(_ S: String, _ T: String) -> Bool {
    
        let S_array = Array(S).reversed().map { (element) -> String in
            return String(element)
        }
        let T_array = Array(T).reversed().map { (element) -> String in
            return String(element)
        }
        
        var s_location = 0
        var t_location = 0
        var s_skip = 0
        var t_skip = 0
        
        while s_location < S.count || t_location < T.count{
            
            while s_location < S.count{
                if S_array[s_location] == "#" {s_skip += 1}
                else if s_skip > 0 {s_skip -= 1}
                else {break}
                s_location += 1
            }
            
            while t_location < T.count{
                if T_array[t_location] == "#" {t_skip += 1}
                else if t_skip > 0 {t_skip -= 1}
                else {break}
                t_location += 1
            }
            
            if s_location < S.count && t_location < T.count{
                
                if S_array[s_location] != T_array[t_location] {return false}
                
            }
            else if (s_location < S.count && t_location >= T.count) || (s_location >= S.count && t_location < T.count ){
                return false
            }
            
            s_location += 1
            t_location += 1
            
        }
        
        
        return true
    }

갑자기 엄청 복잡해 진 느낌입니다. (예 맞습니다...JAVA로 구현되 코드를 보고 어렵게 구현했거든요...)

        let S_array = Array(S).reversed().map { (element) -> String in
            return String(element)
        }
        let T_array = Array(T).reversed().map { (element) -> String in
            return String(element)
        }

일단 거꾸로 가야하기 때문에 이렇게 reverse 해주고 map으로 형태 변환을 해줍니다.

        var s_location = 0 // s의 시작 위치
        var t_location = 0 // t의 시작 위치
        var s_skip = 0 // s에서 #의 갯수
        var t_skip = 0 // t에서 #의 갯수

그리고 이렇게 변수를 추가 해주세요! 그리고 이제 메인 코드를 보겠습니다.

 while s_location < S.count || t_location < T.count{
            
            while s_location < S.count{
                if S_array[s_location] == "#" {s_skip += 1}
                else if s_skip > 0 {s_skip -= 1}
                else {break}
                s_location += 1
            }
            
            while t_location < T.count{
                if T_array[t_location] == "#" {t_skip += 1}
                else if t_skip > 0 {t_skip -= 1}
                else {break}
                t_location += 1
            }
            
            if s_location < S.count && t_location < T.count{
                
                if S_array[s_location] != T_array[t_location] {return false}
                
            }
            else if (s_location < S.count && t_location >= T.count) || (s_location >= S.count && t_location < T.count ){
                return false
            }

그 중에서도 이 코드를 보겠습니다.

            if s_location < S.count && t_location < T.count{
                
                if S_array[s_location] != T_array[t_location] {return false}
                
            }
            else if (s_location < S.count && t_location >= T.count) || (s_location >= S.count && t_location < T.count ){
                return false
            }

가장 헷갈렸던 부분 입니다.

일단 위에서 # 이 있다면 skip 을 증가 시키고 다음 것으 보도록 되어 있죠 

따라서 ba#라면 다음에는 b 부터 보게 되는 코드 입니다.

이러한 while 과정이 끝나면 

둘다 종점에 도달하지 않았을 때, 두 문자가 같은지 확인하고 만약에 틀리다면 같은 문자가 아니라서 false를 반환합니다.

그게 아니라면 이제 한쪽은 끝났는데 다른 한 쪽은 끝나지 않을 때 처리해줘야 합니다.

 

만약 S=  ab#v#v 와 T = v가 주어 졌을 때 , T는 t_location = 1 이 되어 끝나지만 S는 돌려줘야합니다. 

그런데 S가 마지막에 a 가 남는다면 이는 다른 문자이므로 false를 반환해주는 겁니다.

 

끝~!