FilesExpand file tree

 main

/

P82_2.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

52 lines (47 loc) · 2.11 KB

 main

/

P82_2.java

Copy path

Top

File metadata and controls

• Code
• Blame

52 lines (47 loc) · 2.11 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

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

package ch20;

import java.util.HashMap;

import java.util.Map;

public class P82_2 {

public String minWindow(String s, String t) {

// 필요한 문자의 카운터를 정의하는 맵

Map<Character, Integer> need = new HashMap<>();

// 찾아야 하는 문자열의 모든 문자 삽입, 찾아야 하는 문자는 0 이상의 값이 되며,

// 나머지 문자는 모두 0 이하의 값이다.

for (char c : t.toCharArray()) {

need.put(c, need.getOrDefault(c, 0) + 1);

}

// 필요한 문자 전체 카운터 지정

int missing = t.length();

int left = 0, right = 0, start = 0, end = 0;

int minLen = Integer.MAX_VALUE;

// 오른쪽 포인터 이동

for (char c : s.toCharArray()) {

right++;

// 0보다 큰 값이면 필요했던 값이므로 전체 카운터에서 감소

if (need.containsKey(c) && need.get(c) > 0) {

missing--;

}

// need에서 해당 문자는 카운터 감소

need.put(c, need.getOrDefault(c, 0) - 1);

// 필요한 문자 카운터가 0이면 왼쪽 포인터 이동

if (missing == 0) {

// need 값이 0 미만인 경우에는 증가시키며 왼쪽 포인터 계속 이동

while (left < right && need.get(s.charAt(left)) < 0) {

need.put(s.charAt(left), need.getOrDefault(s.charAt(left), 0) + 1);

left++;

}

// 찾은 길이가 기존 최소 길이보다 더 작으면 교체

if (minLen > right - left + 1) {

minLen = right - left + 1;

start = left;

end = right;

}

// 마지막에 빠지는 값은 다시 채워야 하는 값이므로 전체 카운터를 증가시키며 왼쪽 포인터 이동

need.put(s.charAt(left), need.getOrDefault(s.charAt(left), 0) + 1);

missing++;

left++;

}

}

return s.substring(start, end);

}

}