★Minimum Window Substring★

https://leetcode.com/problems/minimum-window-substring/description/

★다시 풀어봐야할 문제★ (굉장히 지저분하게 풀었음, 시간초과 간당간당)

문제 파악 [필수 작성]

문제이해

t의 원소들을 포함하는
s내의 최소길이의 substring

제한 조건 확인

문자열 길이 1~10^5
-> nlogn 아니면 n 만에 풀어라
알파벳 소문자

아이디어

1차 아이디어

t를 dict 형태로 만들고 (k = 알바벳, v = 카운트)
모든 알파벳이 0 이 될때까지 탐색
(s 에서 순차탐색하면서 찾은거 갯수가 t길이만큼됐을때가 모든 원소가 0 이 됐을때)
처음 substring 찾았으면,
맨처음꺼 빼고 substring 끝 다음부터 뺀거 다시 찾기
이런식으로 반복해서 substring 길이 업데이트
만약 substring길이가 지금껏 찾은거중 최소값이면
해당 substring 을 저장

2차 아이디어

미니멈 큐 길이 초기화
빈 큐 초기화
s 큐 초기화
s내의 t조건(t에 있고, count가 0 이상)을 만족하는 갯수 초기화
t 의 counter dict 초기화

큐s에 원소있는동안 계속 pop
t 에 있는 원소 하나 만날때까지 s에서 pop
pop한게 t에 있는 원소면, t 의 counter dict 에서 카운트 빼줌
방금 t 의 counter dict 값이 0 이상 이면
count ++
만약 count == len(t)
현재 큐 길이 를 미니멈 큐 길이와 비교후
만약 더 작으면 미니멈 output 업데이트
while count == len(t):
큐 맨앞 원소 빼고
t 의 counter dict 업데이트
업데이트 했는데 1 이상 값 되면
count --
while 큐 첫번째 원소가 t에 포함된 원소이기 전까지
큐 첫번째 원소 계속 pop

시간복잡도

O(n)

'AABBBBBCAACCCCCCBBB' 'ABBAC'

자료구조

접근 방법 [필수 작성]

자유 형식

코드 구현 [필수 작성]

1차 시도

from collections import Counter
import sys
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        min_len = sys.maxsize
        t_counter = Counter(t)
        count = len(t)
        start_pointer = 0
        end_pointer = 0
        tmp_substring = ""
        tmp_min_substring = ""
        while True:
            print(count)
            while end_pointer < len(s) and count > 0:
                if s[end_pointer] in t_counter:
                    t_counter[s[end_pointer]] -= 1
                    if t_counter[s[end_pointer]] >= 0:
                        count -= 1
                    tmp_substring += s[end_pointer]
                else:
                    tmp_substring += s[end_pointer]
                end_pointer += 1
            if count == 0:
                if len(tmp_substring) < min_len:
                    min_len = len(tmp_substring)
                    tmp_min_substring = tmp_substring
                print(t_counter)
                t_counter[tmp_substring[0]] += 1
                if t_counter[tmp_substring[0]] > 0:
                    count += 1
                tmp_substring = tmp_substring[1:]
            if end_pointer >= len(s):
                break
        return tmp_min_substring

2차 아이디어

1차 시도

구현 복잡해서 갈아엎고 다시 시작

from collections import Counter
from collections import deque
import sys
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        min_sub = ""
        min_q_len = sys.maxsize
        q = deque([])
        s_q = deque(s)
        t_q_num = 0 #현재 q에서 t에 해당하는 갯수 0~len(t)
        t_Counter = Counter(t)

        #q 초기화
        while s_q:
            tmp = s_q.popleft()
            if tmp in t_Counter:
                q.append(tmp)
                t_Counter[tmp] -= 1
                t_q_num += 1
                if t_q_num == len(t):
                    print("".join(q))
                    if min_q_len > len(q):
                        min_q_len = len(q)
                        min_sub = "".join(q)
                    poped = q.popleft()
                    t_Counter[poped] += 1
                    if t_Counter[poped] >= 1:
                        t_q_num -= 1
                break

        while s_q:
            while q and q[0] not in t_Counter:
                q.popleft()
            if t_q_num == len(t):
                print("".join(q))
                if min_q_len > len(q):
                    min_q_len = len(q)
                    min_sub = "".join(q)
                poped = q.popleft()
                t_Counter[poped] += 1
                if t_Counter[poped] >= 1:
                    t_q_num -= 1
                continue
            
            tmp = s_q.popleft()
            q.append(tmp)
            if tmp in t_Counter:
                t_Counter[tmp] -= 1
                if t_Counter[tmp] >= 0:
                    t_q_num += 1
                    if t_q_num == len(t):
                        print("".join(q))
                        if min_q_len > len(q):
                            min_q_len = len(q)
                            min_sub = "".join(q)
                        poped = q.popleft()
                        t_Counter[poped] += 1
                        if t_Counter[poped] >= 1:
                            t_q_num -= 1
                        # while t_q_num == len(t) and q:
                        #     poped = q.popleft()
                        #     if poped in t_Counter:
                        #         t_Counter[poped] += 1
                        #         if t_Counter[poped] >= 1:
                        #             t_q_num -= 1
            print("================================================")
            print("q:",q)
            print("t_Counter:",t_Counter)
            print("t_q_num:",t_q_num)
            
        return min_sub

2차시도

2차 아이디어 1차 시도에서 실패이유는
q에 담긴 것들을 끝까지 안봐주고 끝내버렸기 때문임.

from collections import Counter
from collections import deque
import sys
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        min_sub = ""
        min_q_len = sys.maxsize
        q = deque([])
        s_q = deque(s)
        t_q_num = 0 #현재 q에서 t에 해당하는 갯수 0~len(t)
        t_Counter = Counter(t)

        #q 초기화
        while s_q:
            tmp = s_q.popleft()
            if tmp in t_Counter:
                q.append(tmp)
                t_Counter[tmp] -= 1
                t_q_num += 1
                if t_q_num == len(t):
                    #print("".join(q))
                    if min_q_len > len(q):
                        min_q_len = len(q)
                        min_sub = "".join(q)
                    poped = q.popleft()
                    t_Counter[poped] += 1
                    if t_Counter[poped] >= 1:
                        t_q_num -= 1
                break

        while s_q:
            while q and q[0] not in t_Counter:
                q.popleft()
            if t_q_num == len(t):
                #print("".join(q))
                if min_q_len > len(q):
                    min_q_len = len(q)
                    min_sub = "".join(q)
                poped = q.popleft()
                t_Counter[poped] += 1
                if t_Counter[poped] >= 1:
                    t_q_num -= 1
                continue
            
            tmp = s_q.popleft()
            q.append(tmp)
            if tmp in t_Counter:
                t_Counter[tmp] -= 1
                if t_Counter[tmp] >= 0:
                    t_q_num += 1
                    if t_q_num == len(t):
                        #print("".join(q))
                        if min_q_len > len(q):
                            min_q_len = len(q)
                            min_sub = "".join(q)
                        poped = q.popleft()
                        t_Counter[poped] += 1
                        if t_Counter[poped] >= 1:
                            t_q_num -= 1
            # print("================================================")
            # print("q:",q)
            # print("t_Counter:",t_Counter)
            # print("t_q_num:",t_q_num)
        if t_q_num == len(t):
            if min_q_len > len(q):
                min_q_len = len(q)
                min_sub = "".join(q)
        while q:
            if q[0] in t_Counter:
                if t_q_num == len(t):
                    if min_q_len > len(q):
                        min_q_len = len(q)
                        min_sub = "".join(q)
            poped = q.popleft()
            if poped in t_Counter:
                t_Counter[poped] += 1
                if t_Counter[poped] >= 1:
                    t_q_num -= 1
            # print("================================================")
            # print("q:",q)
            # print("t_Counter:",t_Counter)
            # print("t_q_num:",t_q_num)
        return min_sub

→ 뭔가 최적화에 문제가 있음

3차 시도

from collections import Counter
from collections import deque
import sys
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        min_sub = ""
        min_q_len = sys.maxsize
        q = deque([])
        s_q = deque(s)
        t_q_num = 0 #현재 q에서 t에 해당하는 갯수 0~len(t)
        t_Counter = Counter(t)

        #q 초기화
        while s_q:
            tmp = s_q.popleft()
            if tmp in t_Counter:
                q.append(tmp)
                t_Counter[tmp] -= 1
                t_q_num += 1
                if t_q_num == len(t):
                    #print("".join(q))
                    if min_q_len > len(q):
                        min_q_len = len(q)
                        min_sub = "".join(q)
                    poped = q.popleft()
                    t_Counter[poped] += 1
                    if t_Counter[poped] >= 1:
                        t_q_num -= 1
                break

        #s_q 진행
        while s_q:
            while q and q[0] not in t_Counter:
                q.popleft()
            if t_q_num == len(t):
                #print("".join(q))
                if min_q_len > len(q):
                    min_q_len = len(q)
                    min_sub = "".join(q)
                poped = q.popleft()
                t_Counter[poped] += 1
                if t_Counter[poped] >= 1:
                    t_q_num -= 1
                continue
            
            tmp = s_q.popleft()
            q.append(tmp)
            if tmp in t_Counter:
                t_Counter[tmp] -= 1
                if t_Counter[tmp] >= 0:
                    t_q_num += 1
                    if t_q_num == len(t):
                        #print("".join(q))
                        if min_q_len > len(q):
                            min_q_len = len(q)
                            min_sub = "".join(q)
                        poped = q.popleft()
                        t_Counter[poped] += 1
                        if t_Counter[poped] >= 1:
                            t_q_num -= 1
            #print("================================================")
            #print("q:",q)
            #print("s_q:",s_q)
            #print("t_Counter:",t_Counter)
            #print("t_q_num:",t_q_num)

        #s_q 다 끝나고 남은 q진행
        while q and t_q_num == len(t):
            if min_q_len > len(q):
                min_q_len = len(q)
                min_sub = "".join(q)
            poped = q.popleft()
            if poped in t_Counter:
                t_Counter[poped] += 1
                if t_Counter[poped] >= 1:
                    t_q_num -= 1
                    if t_q_num != len(t):
                        break
            #print("================================================")
            #print("s_q:",s_q)
            #print("q:",q)
            #print("t_Counter:",t_Counter)
            #print("t_q_num:",t_q_num)
        return min_sub

배우게 된 점 [필수 작성]

자유 형식

질문 [ 필수 X ]

Q.3차 시도

해설코드와 로직이 똑같은데, 실행시간이 최악인 경우입니다.

while 문을 살펴보고, print 문을 찍어보아도 의도대로 중복되는 부분없이 잘 도는것 같은데 어느부분에서 비효율이 발생하는지 잘 모르겠습니다.

비효율이 발생하는 부분과 코드를 리팩토링할 수 있는 방법을 알려주시면 감사드리겠습니다.

→ 즉, 해설코드는 index를 통해서 s 에 접근한다.

답변

해설 코드와 논리는 같지만 가장 큰 차이는 t에 해당하지 않는 문자는 저장하지 않는다는 점입니다. 해설 코드의 경우 문자와 인덱스를 같이 입력하여 popleft를 할 때 인덱스를 통해 t에 해당하지 않는 문자를 스킵하기에 불필요한 연산이 배제됩니다.