어제 드디어 투 포인터 문제를 전부 풀었다. 물론 150 인터뷰 내에 있는 그 범위의 문제를 말한다.
오늘은 슬라이딩 윈도우가 주제이다.
209. Minimum Size Subarray Sum
이게 왜 슬라이딩인지 이해가 안되어서 해설을 읽고 코드를 작성해봤다.
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0;
int right = 0;
int currentSum = nums[left];
int minLength = nums.length;
boolean check = false;
while(left < nums.length){
if ((currentSum <= target) && (right < nums.length-1)){
right++;
currentSum+=nums[right];
}else{
currentSum-= nums[left];
left++;
}
if (currentSum == target){
check = true;
if (minLength > (right - left + 1)){
minLength = right - left + 1;
}
}
}
if (!check) {
return 0;
}
return minLength;
}
}
이 코드의 문제는
이부분이 통과가 되지 않는다는 거다.
2, 4, 5 가 되어야하는 것 같은데 내가 푼 방식은 무조건 나열된 수가 아니면 안된다... 근데 문제 풀이 해주신 분은 해결하시길래 코드를 살펴봤다.
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0;
int minLen = Integer.MAX_VALUE;
int curSum = 0;
for (int right = 0; right < nums.length; right++){
curSum += nums[right];
while (curSum >= target){
if (right - left + 1 < minLen){
minLen = right - left + 1;
}
curSum -= nums[left];
left++;
}
}
return minLen != Integer.MAX_VALUE ? minLen : 0;
}
}
으으음...
왜 다른 건지 감이 안 온다..
왜 같은 값일 때 minLen의 값을 변경하지 않은걸까...
이해가 되었다. 문제를 잘 읽지 않은 내 탓이었다.
3. Longest Substring Without Repeating Characters
이게 왜 슬라이딩 윈도우..?
class Solution {
public int lengthOfLongestSubstring(String s) {
int left = 0;
int maxLen = 0;
for (int right = 0; right < s.length(); right++){
String subString = s.substring(left, right);
System.out.println(subString);
if (subString.indexOf(s.charAt(right))!=-1){
while((subString.indexOf(s.charAt(right))!=-1)&&left < right){
left++;
}
}
if (maxLen < (right - left + 1 )){
maxLen = right - left + 1;
}
}
return maxLen;
}
}처음엔 이렇게 풀었느데.. 저 substring 에서 헷갈려서 포기해버렸다.
저거 [left, right) 이런 형식이라서 뭔가 if 순서가 잘못된건지 뭔지 모르겠지만... 여튼 머리가 아파왔다.
class Solution {
public int lengthOfLongestSubstring(String s) {
int left = 0;
int maxLen = 0;
HashSet<Character> charSet = new HashSet<>();
for (int right = 0; right < s.length(); right++) {
while (charSet.contains(s.charAt(right))) {
charSet.remove(s.charAt(left));
left++;
}
charSet.add(s.charAt(right));
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
}이분은 간단하게 Hashset 을 써서 푸셨다.
여기에서 remove 하는게 좀 오래걸리니아래와 같이 조금 개선한 버전도 있었다.
class Solution {
public int lengthOfLongestSubstring(String s) {
int maxLength = 0;
int left = 0;
Map<Character, Integer> count = new HashMap<>();
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
count.put(c, count.getOrDefault(c, 0) + 1);
while (count.get(c) > 1) {
char leftChar = s.charAt(left);
count.put(leftChar, count.get(leftChar) - 1);
left++;
}
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
}python으로 치면 dict 에서 값을 +1 하거나 -1 을 하면서 찾는 방식이였는데 테스트 결과에서 확실히 빠르게 나왔다.
요즘 갑자기 드는 생각인데 멘토님들께 이거 모르겠어요 라고 가져가면 멘토님들은 3초면 풀이방법을 찾으신다.
대부분 기업들에서 비슷한 문제를 겪고 해결한 블로그들이였다.
그래서 뭐랄까... 읽으면 좋지 않을까? 싶긴 한데 역시 시작이 가장 어려운 것 같다.
하나를 스윽스윽 읽는데 뭔가 급하게 필요하지 않으니 눈에도 잘 들어오지 않는다.
그래서 어떻게 하면 재밌고 즐겁게 읽을 수 있을지 고민중이다. 오늘 안에 답이 나오면 참 좋을 것 같은데 어떨런지 모르겠다.