(Leetcode) 76 - Minimum Window Substring 풀이
기회가 되어 달레님의 스터디에 참여하여 시간이 될 때마다 한문제씩 풀어보고 있다.
https://leetcode.com/problems/minimum-window-substring/description/
내가 작성한 풀이
문제 자체는 엄청 어렵지는 않았다. 다만 어떻게 최적화 해볼 수 있을까 고민하는데 많은 시간이 필요했다.
컨셉은 기본적으로 window 를 사용했다는 것으로 동일하다.
필요한 문자들이 무엇인지 확인하기 위해 counter 변수를 사용한다. 우선 start를 0으로 고정시킨 상태로 오른쪽으로 1칸씩 window를 늘리며 필요한 모든 문자가 포함되었는지 확인한다. minLength와 minLengthStart 값을 찾게되면 거기서부터는 start도 1씩 늘리면서 minLength를 찾아나간다.
버전 1
class Solution {
public String minWindow(String s, String t) {
if (s.length() < t.length()) {
return "";
}
Map<Character, Integer> counter = new HashMap<>();
for (int i = 0; i < t.length(); i++) {
counter.merge(t.charAt(i), 1, Integer::sum);
}
int start = 0;
int minLength = 0;
int minStart = 0;
for (int i = 0; i < s.length(); i++) {
// update counter
char currentChar = s.charAt(i);
Integer count = counter.get(currentChar);
if (count != null) {
counter.merge(currentChar, -1, Integer::sum);
} else {
continue;
}
// check all count is 0 -> update min;
while (validate(counter)) {
int currentLength = i + 1 - start;
if (minLength > currentLength || minLength == 0) {
minStart = start;
minLength = currentLength;
}
// try to move start to start + 1
// increase count if front char exist in counter
count = counter.get(s.charAt(start));
if (count != null) {
if (count == 0) {
break;
}
counter.put(s.charAt(start), count + 1);
}
start++;
}
}
return s.substring(minStart, minStart + minLength);
}
private boolean validate(Map<Character, Integer> counter) {
for (int count : counter.values()) {
if (count > 0) {
return false;
}
}
return true;
}
}
TC, SC
문제에 다음과 같이 제시되어 있다.
m == s.length
n == t.length
시간 복잡도는 O(n * m), 공간 복잡도는 O(n) 이다.
버전 2: 성능 우선 버전
사실 이 버전은 실제 어플리케이션에서는 쓰지 않을지도 모르겠다. 이해하는데 좀 더 시간이 걸릴 것 같기 때문이다.
class Solution {
public String minWindow(String s, String t) {
if (s.length() < t.length()) {
return "";
}
Integer[] counter = new Integer[123]; // 적당히 넉넉한 배열 할당
char[] mustContainCharArray = t.toCharArray();
for (char mustContainChar : mustContainCharArray) {
int count = counter[mustContainChar] == null ? 0 : counter[mustContainChar];
count = count + 1;
counter[mustContainChar] = count;
}
int start = 0;
int minLength = 0;
int minLengthFrom = 0;
for (int i = 0; i < s.length(); i++) {
char currentChar = s.charAt(i);
Integer count = counter[currentChar];
if (count != null) {
count = count - 1;
counter[currentChar] = count;
}
// check all count is 0 -> update min;
while (validate(counter)) {
int currentLength = i + 1 - start;
if (minLength > currentLength || minLength == 0) {
minLengthFrom = start;
minLength = currentLength;
}
// try to move start to start + 1
// increase count if front char exist in counter
count = counter[s.charAt(start)];
if (count != null) {
if (count == 0) {
break;
}
counter[s.charAt(start)] = count + 1;
}
start++;
}
}
return s.substring(minLengthFrom, minLengthFrom + minLength);
}
private boolean validate(Integer[] counter) {
for (int i = 65; i < counter.length; i++) { // 65부터 알파벳이 시작하기 때문에 그 이전 값은 의미없다.
Integer count = counter[i];
if (count == null) {
continue;
}
if (count > 0) {
return false;
}
}
return true;
}
}
시간이 개선되었다.
TC, SC
문제에 다음과 같이 제시되어 있다.
m == s.length
n == t.length
시간 복잡도는 O(n*m), 공간 복잡도는 O(1) 이다. 표현상으로는 시간복잡도는 동일하나 실제 실행 시간은 줄어들었고, 공간복잡도는 줄어들게 되었다.