https://leetcode.com/problems/minimum-window-substring/
각 m와 n의 길이를 가진 s와 t라는 string이 주어집니다. t가 가진 모든 글자를 포함(중복되는 글자도 고려)하는 s의 부분 문자열 중 가장 작은 값을 구하시오. 해당되는 값이 없다면 빈 문자열을 반환합니다.
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
해설: A, B, C 를 포함하는 가장 작은 s의 부분 문자열은 BANC 이다.
Input: s = "a", t = "a"
Output: "a"
Input: s = "a", t = "aa"
Output: ""
해설: a, a 를 포함하는 가장 작은 s의 부분 문자열이 없으므로 빈 문자열을 반환한다.
슬라이딩 윈도우 알고리즘 문제입니다.
s를 처음부터 끝까지 돌며 t가 가진 모든 글자를 포함한 윈도우를 유효한 윈도우로 지정합니다. 유효한 윈도우 중 가장 작은 크기의 윈도우를 구합니다.
우선 두 개의 Counter 객체를 생성합니다.
하나는 t 문자열에 관한 카운터 (t 문자열 중 어떤 글자가 더 필요한지 알아보기 위한 용도),
하나는 현재 window에 해당하는 부분 문자열에 대한 카운터입니다.
따라서 각각 Counter(t), 빈 카운터로 시작합니다.
from collections import Counter
class Solution:
def minWindow(self, s: str, t: str) -> str:
required_counter, window_counter = Counter(t), Counter()
# if t = 'ABC'
# required_counter would be {A:1,B:1,C:1}
# window_counter would be {}
# if t = 'aa'
# required_counter would be {a:2}
그리고 포인터를 선언해줍니다.
슬라이딩 윈도우 기법으로 탐색해야 하기에 투 포인터를 활용합니다. 두 포인터 모두 0번 인덱스에서 시작하도록 합니다.
from collections import Counter
class Solution:
def minWindow(self, s: str, t: str) -> str:
required_counter, window_counter = Counter(t), Counter()
pointer_left = pointer_right = 0
유효한 윈도우를 찾았을 때 해당 위치도 기억하고 있어야 하므로 window_left, window_right이라는 추가적인 포인터도 선언합니다.
저는 그냥 undefined 상태로 선언만 해두었습니다.
from collections import Counter
class Solution:
def minWindow(self, s: str, t: str) -> str:
required_counter, window_counter = Counter(t), Counter()
pointer_left = pointer_right = 0
window_left = window_right = None
required_length라는 t의 길이를 값으로 가진 추가적인 변수도 생성합니다.
t에 해당하는 글자를 하나씩 찾을때마다 -1 해줄 예정입니다. 그러면 0이 된다면 조건을 충족했다는 뜻이 될 것이며,
일종의 for문 break용 플래그로 쓰일 수 있을 겁니다.
from collections import Counter
class Solution:
def minWindow(self, s: str, t: str) -> str:
required_counter, window_counter = Counter(t), Counter()
pointer_left = pointer_right = 0
window_left = window_right = None
required_length = len(t)
이제 이중 for문을 만들어줍니다.
밖에 있는 for문은 pointer_left가 s 문자열의 범위를 벗어나지 않도록 하고, (여기 빠져나가면 탐색 종료)
안쪽에 있는 for문은 pointer_right가 t 문자열에 포함된 글자를 모두 찾거나, 마찬가지로 s 문자열의 범위를 벗어날 때까지 돕니다.
from collections import Counter
class Solution:
def minWindow(self, s: str, t: str) -> str:
required_counter, window_counter = Counter(t), Counter()
pointer_left = pointer_right = 0
window_left = window_right = None
required_length = len(t)
while pointer_left < len(s):
while required_length != 0 and pointer_right < len(s):
우 포인터 for문 로직
from collections import Counter
class Solution:
def minWindow(self, s: str, t: str) -> str:
required_counter, window_counter = Counter(t), Counter()
pointer_left = pointer_right = 0
window_left = window_right = None
required_length = len(t)
while pointer_left < len(s):
while required_length != 0 and pointer_right < len(s):
right_char = s[pointer_right]
window_counter[right_char] += 1
# 👆🏻 현재 우 포인터 위치에 놓인 글자를 윈도우에 추가
if required_counter[right_char] >= window_counter[right_char]:
required_length -= 1
# 👆🏻 현재 글자가 조건을 충족하기 위해 더 필요한 글자라면 required_length - 1
pointer_right += 1
# 👆🏻 우 포인터 우측으로 한 칸 이동
좌 포인터 for문 로직
from collections import Counter
class Solution:
"""
# EXAMPLE
# s = 'AD0BEC0DEBANC'
# t = 'ABC'
# should return 'BANC'
"""
def minWindow(self, s: str, t: str) -> str:
required_counter, window_counter = Counter(t), Counter()
pointer_left = pointer_right = 0
window_left = window_right = None
required_length = len(t)
while pointer_left < len(s):
while required_length != 0 and pointer_right < len(s):
right_char = s[pointer_right]
window_counter[right_char] += 1
if required_counter[right_char] >= window_counter[right_char]:
required_length -= 1
pointer_right += 1
left_char = s[pointer_left]
if required_length == 0:
# 👆🏻 필요한 글자수롤 모두 채웠다면
if window_left is None or window_right - window_left > pointer_right - pointer_left:
window_left, window_right = pointer_left, pointer_right
# 👆🏻 지금 기억하고 있는 가장 작은 윈도우 사이즈보다 현재 좌우포인터 간격이 더 작다면 재할당
window_counter[left_char] -= 1
# 👆🏻 윈도우에서 현재 좌 포인터에 해당하는 글자 제거
if required_counter[left_char] > window_counter[left_char]:
required_length += 1
# 👆🏻 좌 포인터의 글자를 지우고 보니 요구 조건 충족이 안된다면, required_length 1 추가
pointer_left += 1 # 좌 포인터 한 칸 이동
전체 코드
from collections import Counter
class Solution:
"""
# EXAMPLE
# s = 'AD0BEC0DEBANC'
# t = 'ABC'
# should return 'BANC'
"""
def minWindow(self, s: str, t: str) -> str:
required_counter, window_counter = Counter(t), Counter()
pointer_left = pointer_right = 0
window_left = window_right = None
required_length = len(t)
while pointer_left < len(s):
while required_length != 0 and pointer_right < len(s):
right_char = s[pointer_right]
window_counter[right_char] += 1
if required_counter[right_char] >= window_counter[right_char]:
required_length -= 1
pointer_right += 1
left_char = s[pointer_left]
if required_length == 0:
if window_left is None or window_right - window_left > pointer_right - pointer_left:
window_left, window_right = pointer_left, pointer_right
window_counter[left_char] -= 1
if required_counter[left_char] > window_counter[left_char]:
required_length += 1
pointer_left += 1
return s[window_left:window_right] if window_left is not None else ''
그나저나 문제에 나오는 인수 이름 진짜 그지같은듯..... s, t가 뭐냐 s, t가...............
[정렬 알고리즘 시리즈] 버블정렬(Bubble Sort) (0) | 2022.05.07 |
---|---|
프로그래머스 / 올바른 괄호 / level2 / 파이썬 (0) | 2021.12.19 |
파이썬의 딕셔너리는 어떻게 구현되어 있을까? -해시- (2) | 2021.04.04 |
백준 / DFS / 2667 : 단지번호 붙이기 / 파이썬 (0) | 2021.03.23 |
프로그래머스 / 크레인 인형뽑기 게임 / level 1 / 파이썬 (1) | 2021.03.21 |
댓글 영역