[1스4코2파] #137. LeetCode Pattern 844. Backspace String Compare

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (137일차)
[4코1파] 2023.01.13~ (128일차)
[1스4코1파] 2023.04.12~ (39일차)
[1스4코2파] 2023.05.03 ~ (18일차)

Today :

2023.05.20 [137일차]
LeetCode Patterns
844. Backspace String Compare

844. Backspace String Compare

문제 설명

s,t 각 문자열을 담은 변수가 있는데
해당 문자열 안에는 '#' 이 담겨 있을 수도, 없을 수도 있다.
여기서 문자열 '#'은 backspace를 의미하는데,
해당 s, t 문자열을 수행했을 때 값이 같으면 true, 아니면 false를 return 한다.

예를 들어서 s = 'ab#c', t='ad#c' 인데,
#이 backspace를 의미하므로 s를 수행하면 s = 'ac'가 되고, t='ac'가 되기 때문에 true이다.
그러나 example3 처럼 s = 'a#c', t='b' 일경우에는 s='c', t='b' 이므로 fales 인 것이다 !

문제 풀이 방법

제약 사항에 O(n) 인 것을 O(1) 로 풀어보라고 하고 있음
에효
일단 내머리에서 나올 수 있는건 queue, stack 으로 푸는 방법 뿐 ㅋㅎ

내 코드

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        s_que, t_que = deque(s), deque(t)
        s_stack, t_stack = [], []

        while s_que:
            s1 = s_que.popleft()
            if s1!='#':
                s_stack.append(s1)

            else:
                if len(s_stack)!=0:
                    s_stack.pop()

        while t_que:
            t1 = t_que.popleft()
            if t1!='#':
                t_stack.append(t1)
            else:
                if len(t_stack)!=0:
                    t_stack.pop()

        return True if s_stack==t_stack else False

증빙

여담

시간복잡도 O(1) 인 풀이는..

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        s_pos = len(s) - 1
        t_pos = len(t) - 1

        def skip(item, pos):
            skip = 0
            while item[pos] == '#':
                skip += 1
                pos -= 1

            while pos >= 0 and skip > 0:
                if item[pos] != '#':
                    skip -= 1
                else:
                    skip += 1
                pos -= 1
            
            return pos

        while s_pos >= 0 or t_pos >= 0:
            while s[s_pos] == '#':
                s_pos = skip(s, s_pos)
            while t[t_pos] == '#':
                t_pos = skip(t, t_pos)

            s_c = '' if s_pos < 0 else s[s_pos]
            t_c = '' if t_pos < 0 else t[t_pos]
            if s_c != t_c:
                return False

            if s_pos >= 0:
                s_pos -= 1

            if t_pos >= 0:
                t_pos -= 1

        return True

복잡도는 낮은데 코드 복잡도 무슨일이냐;