FilesExpand file tree

 main

/

yyyyyyyyyKim.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

37 lines (31 loc) · 1.49 KB

 main

/

yyyyyyyyyKim.py

Top

File metadata and controls

• Code
• Blame

37 lines (31 loc) · 1.49 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

class Solution:

def minWindow(self, s: str, t: str) -> str:

# 슬라이딩 윈도우(시간복잡도 O(m+n), 공간복잡도 O(n) : m=len(s), n=len(t))

# 필요한 문자 개수 딕셔너리로 정리

need = {}

for i in t:

need[i] = need.get(i,0) + 1

window = {} # 현재 윈도우에 포함된 문자 개수 딕셔너리로 정리

have = 0 # 조건을 만족한 문자 수

need_count = len(need) # 조건을 만족해야하는 문자 수

min_len = 100001 # 최소윈도우길이(최대값을 초기값으로 설정)

answer = ""

left = 0

# 오른쪽 포인터 이동

for right in range(len(s)):

window[s[right]] = window.get(s[right],0) + 1

# 해당 문자가 조건을 만족했다면 have += 1

if s[right] in need and window[s[right]] == need[s[right]]:

have += 1

# 모든 조건 만족하면 왼쪽 계속 줄이기

while have == need_count:

# 최소 윈도우 길이 갱신

if (right - left + 1) < min_len:

min_len = right - left + 1

answer = s[left:right+1]

# 윈도우 왼쪽 문자 제거

window[s[left]] -= 1

if s[left] in need and window[s[left]] < need[s[left]]:

have -= 1

left += 1

return answer