javascript 코딩테스트 - 슬라이딩 윈도우

슬라이딩 윈도우는 창문이 있을 때 그 너비나 높이에 따라서 보이는 부분이 다르고, 또 창문을 옆으로 이동시키면서 자료구조를 다루는 알고리즘이다.

 

문제1

Given an array of integers and a number, write a function called maxSubarraySum, which finds the maximum sum of a subarray with the length of the number passed to the function.

Note that a subarray must consist of consecutive elements from the original array. In the first example below, [100, 200, 300] is a subarray of the original array, but [100, 300] is not.

 

maxSubarraySum([100,200,300,400], 2) // 700
maxSubarraySum([1,4,2,10,23,3,1,0,20], 4)  // 39 
maxSubarraySum([-3,4,0,-2,6,-1], 2) // 5
maxSubarraySum([3,-2,7,-4,1,-1,4,-2,1],2) // 5
maxSubarraySum([2,3], 3) // null

 

숫자 배열과 부분 배열의 길이를 주고 길이만큼 이웃한 숫자들의 합 중 최대값을 구하는 문제이다.

 

처음 든 생각

- 길이가 정해져있으므로 그거에 맞춰서 추가되는 애를 더하고 빠지는 애를 빼주면 되겠다.

- 최대값 변수를 따로 선언해주고 얘랑 하나씩 비교해가면 되겠다.

 

나의 답

function maxSubarraySum(arr,num){
  // 배열의 길이가 부분배열의 길이보다 작으면 null 출력
  if(arr.length <num){
      return null
  }
 
  let max =0
  
  // 숫자들의 합 중 처음 나올 값 설정
  for(let i=0; i<num;i++){
      max += arr[i]
  }
  
  let temp = max
  
  // num의 크기르 가진 윈도우를 옆으로 한칸씩 이동하면서 합을 계산한 후 최대값과 비교
  for(let i =1; i<arr.length-num+1; i++){
      let sum = temp + arr[i+num-1] -arr[i-1]
      max = Math.max(max,sum)
      temp = sum
  }
    return max
}

윈도우의 사이즈도 고정되어있고 단순 옆으로 이동하면서 비교만 하면 되는 거라 어렵지는 않았다.

 

문제2

 

Write a function called minSubArrayLen which accepts two parameters - an array of positive integers and a positive integer.This function should return the minimal length of a contiguous subarray of which the sum is greater than or equal to the integer passed to the function. If there isn't one, return 0 instead.
Examples:

minSubArrayLen([2,3,1,2,4,3], 7) // 2 -> because [4,3] is the smallest subarray
minSubArrayLen([2,1,6,5,4], 9) // 2 -> because [5,4] is the smallest subarray
minSubArrayLen([3,1,7,11,2,9,8,21,62,33,19], 52) // 1 -> because [62] is greater than 52
minSubArrayLen([1,4,16,22,5,7,8,9,10],39) // 3
minSubArrayLen([1,4,16,22,5,7,8,9,10],55) // 5
minSubArrayLen([4, 3, 3, 8, 1, 2, 3], 11) // 2
minSubArrayLen([1,4,16,22,5,7,8,9,10],95) // 0

 

배열과 양의 정수를 받아 이웃한 숫자들의 합이 목표값보다 크게 만드는 숫자들의 개수 중 최솟값을 출력하는 문제이다. 만족하는 숫자 조합이 없으면 0 출력

 

처음 든 생각

- 윈도우의 크기가 바뀌는 문제네

- 아이템을 하나 덧셈하거나 뺄셈을 하면서 목표값과 계속 비교를 해야겠다.

 

나의 답

const minSubArrayLen = (arr, num) =>{
	// 배열 없으면 0 리턴
    if(arr.length === 0){
        return 0
    }
    
    // 초기값 설정 - 포인터 두 개
    let i=0
    let j=0
    let sum=arr[0]
    let answer = Infinity
    
    // j포인터를 기준으로 반복문
    while(j<arr.length){
    	// 목표값보다 작으면 오른쪽으로 이동하여 아이템 하나 추가
        if(sum<num){
            j++
            sum+=arr[j]
        }
        // 목표값 이상이면 답 설정해놓고 하나씩 줄여본다
        if(sum>=num){
            answer = Math.min(j-i+1, answer)
            sum-=arr[i]
            i++
        }
    }
    return answer === Infinity ? 0 : answer
}

슬라이딩 윈도우 문제이지만 윈도우의 크기가 변한다는 점에서 저번에 배웠던 다중 포인터를 접목시켜서 풀었다. 전체적인 윈도우는 오른쪽으로 이동하지만 크기가 변할 때는 포인터를 활용해서 푸는 것이 좋을 것 같다.

 

문제3

 

Write a function called findLongestSubstring, which accepts a string and returns the length of the longest substring with all distinct characters.

findLongestSubstring('') // 0
findLongestSubstring('rithmschool') // 7
findLongestSubstring('thisisawesome') // 6
findLongestSubstring('thecatinthehat') // 7
findLongestSubstring('bbbbbb') // 1
findLongestSubstring('longestsubstring') // 8
findLongestSubstring('thisishowwedoit') // 6

 

문자열을 받아 겹치지 않는 알파벳을 가진 부분문자열의 최대길이를 묻는 문제이다.

 

처음 든 생각

- 문제2와 같이 포인터를 두 개 두어 하나씩 추가될 때마다 includes로 포함여부를 확인해야겠다.

- 포함되어있지 않다면 하나씩 늘리고, 포함되어있다면 왼쪽 포인터를 줄인다.

 

나의 답

function findLongestSubstring(str){
  // 문자열 길이가 1이하인 경우 따로 처리
  if(str.length <=1){
      return str.length
  }
  
  // 포인터 및 초기값 설정
    let i = 0
    let j = 1 
    let answer = 0
    let tmpStr =str[0]
    
    while(j<str.length){
    
    	// 포함되어있다면 왼쪽에서 한 칸 줄인다.
        if(tmpStr.includes(str[j])){
            i++
            tmpStr = tmpStr.substring(1)
        } 
        
        // 포함되어있지 않다면 오른쪽 하나씩 늘리고 답을 계속 갱신
        else{
            tmpStr +=str[j]
            answer = Math.max(tmpStr.length, answer)
            j++
        }
    }
    return answer
}

문제 2번과 거의 똑같은 구조였다. 문제2는 대소비교를 하고 이 문제는 포함여부를 판단한다는 점만 다를 뿐 거의 구조는 똑같았다. 

슬라이딩 윈도우 + 다중 포인터 구조의 문제는 복습을 많이 하면 유용하게 써먹을 수 있을 것 같다.

 

문제 3번의 다른 답을 가져와봤다.

findLongestSubstring 솔루션
function findLongestSubstring(str) {
  let longest = 0;
  let seen = {};
  let start = 0;
 
  for (let i = 0; i < str.length; i++) {
    let char = str[i];
    if (seen[char]) {
      start = Math.max(start, seen[char]);
    }
    // index - beginning of substring + 1 (to include current in count)
    longest = Math.max(longest, i - start + 1);
    // store the index of the next char so as to not double count
    seen[char] = i + 1;
  }
  return longest;
}

여기서는 객체 구조를 활용하여 문자별로 있는지 없는지를 판단하는 것으로 구성을 했다.

겹치는 게 없으면 계속해서 길이를 추가한다는 점에서는 똑같았지만 해당 알파벳이 몇번째 위치에 있는지를 기억하도록 객체에 값을 설정해준다. 

만약 겹치는 게 있다면 시작 지점을 겹치는 알파벳 바로 다음부터 카운팅을 할 수 있게 start 값을 바꾼 다음 답을 업데이트한다. 그리고 겹쳐졌던 알파벳의 위치도 뒤에 오는 순서로 업데이트한다.

 

가장 결정적으로 다른 점은 시작점을 바꾸는 구조이다. 나의 답은 왼쪽으로 하나씩 줄여가면서 계속 비교를 하지만 위의 솔루션에서는 겹치는 게 보이면 왼쪽 포인터를 바로 겹치는 문자 다음으로 한 번에 끌고 온다는 점에서 더 나은 알고리즘이라고 볼 수 있다. 포인터를 효율적으로 이동시키는 부분에 대해서도 고려하면서 알고리즘을 구성하면 좋을 것 같다.