알고리즘 풀이 5)1-5 (투포인터 알고리즘, 슬라이드윈도우)

투 포인터라는 개념을 전혀 모르고 기존에 알고있는 방법으로만 풀었는데

강의를 들어보면서 시작복잡도 개선을 위해 투 포인터 알고리즘으로 문제를 풀이하는 방법을 배웠다.

 

 

Section5_1번: 두 배열 합치기 (배열의 합집합)

//--------------투포인터 풀이-----------------
function solution5_1_1(arr1: number[], arr2: number[]): number[] {
  let answer: number[] = [];
  let len1 = arr1.length;
  let len2 = arr2.length;
  let p1 = 0;
  let p2 = 0;
  while (p1 < len1 && p2 < len2){  // 둘중 하나가 거짓이면 전체가 거짓
      if(arr1[p1] <= arr2[p2]) answer.push(arr1[p1++]);  // p1 추가 하고 , p1++
      else answer.push(arr2[p2++]);
  }
  while (p1 < len1) answer.push(arr1[p1++]);
  while (p2 < len2) answer.push(arr2[p2++]); 
  return answer;
}
console.log(solution5_1_1([1, 3, 5], [2, 3, 6, 7, 9]));

//------------ 나의 이전 풀이 (sort)-----------
function solution5_1(arr1: number[], arr2: number[]): Array<number> {
  return [...arr1, ...arr2].sort();
}
console.log(solution5_1([1, 3, 5], [2, 3, 6, 7, 9]));

 

 

Section5_2번: 공통 원소 구하기 (배열의 교집합)

//---------------투포인터 풀이-----------------------
function solution5_2_1(arr1: number[], arr2: number[]): number[] {
  let p1 = 0;
  let p2 = 0;
  let len1 = arr1.length;
  let len2 = arr2.length;
  let answer: number[] = [];

  arr1.sort((a, b) => a - b);
  arr2.sort((a, b) => a - b);

  while (p1 < len1 && p2 < len2) {
    if (arr1[p1] === arr2[p2]) {
      answer.push(arr1[p1++]);
      p2++;
    } else if (arr1[p1] > arr2[p2]) p2++;
    else p1++;
  }
  return answer;
}
console.log(solution5_2_1([1, 3, 9, 5, 2], [3, 2, 5, 7, 8]));

// ----------나의 이전 풀이(filter & sort)------------
function solution5_2(arr1: number[], arr2: number[]): string {
  return arr1.filter(num => arr2.includes(num)).sort().join(" ");
}
console.log(solution5_2([1, 3, 9, 5, 2], [3, 2, 5, 7, 8]));

 

 

Section5_3번: 연속 부분 수열 1

//------------투포인터 풀이----------------
function solution5_3_1(m: number, arr: number[]) {
  let answer = 0;
  let startP = 0;
  let sum = 0;
  for (let endP = 0; endP < arr.length; endP++) {
    sum += arr[endP];
    
    //일단 합이 6이면 경우의수 +1
    if (sum === m) answer++; //end 포인트 추가해서 6인지

    //합이 6이상이면 더 추가할 필요가 없으므로,
    while (sum >= m) {
      //다음 시작점에서 탐색
      sum -= arr[startP++]; // -> sum -= arr[startP] 하고 startP++

      //시작점 바꾸자마자 6이라면 -> 경우의 수+1
      if (sum === m) answer++;
    }
  }
  return answer;
}
console.log(solution5_3_1(6, [1, 2, 1, 3, 1, 1, 1, 2]));

//-------- 나의 풀이 (이중 for문)------
function solution5_3(N: number, M: number, arr: number[]): number {
  let count = 0;
  for (let i = 0; i < N; i++) {
    let sum = 0;
    for (let j = i; j < N; j++) {
      sum += arr[j];
      if (sum < M) continue;
      if (sum === M) {
        count++;
      }
      break;
    }
  }
  return count;
}
console.log(solution5_3(8, 6, [1, 2, 1, 3, 1, 1, 1, 2]));

  * while 문으로 시간복잡도를 개선한 다른 코드

function solution(m, arr) {
  let answer = 0;
  let sum = 0;
  let startP = 0;
  let endP = 0;
  while (endP < arr.length) {
    if (sum < m) {
      sum += arr[endP++];
    } else if (sum === m) {
      answer++;
      sum -= arr[startP++];
    } else {
      sum -= arr[startP++];
    }
  }
  return answer;
}
console.log(solution(6, [1, 2, 1, 3, 1, 1, 1, 2]));

 

 

Section5_4번: 연속 부분 수열 2

//----------------투포인터 풀이-------------
function solution5_4_1(m: number, arr: number[]) {
  let answer = 0, sum = 0, startP = 0;
  for (let endP = 0; endP < arr.length; endP++) {
    sum += arr[endP];
    while (sum > m) {
      sum -= arr[startP++];
    }
    answer += endP - startP + 1; // endP ~ startP로 만들 수 있는 연속 수열의 개수
  }
  return answer;
}
console.log(solution5_4_1(5, [1, 3, 1, 2, 3]));

//-----------나의 풀이(이중 for문)-------------
function solution5_4(N: number, M: number, arr: number[]): number {
  let count = 0;
  for (let i = 0; i < N; i++) {
    let sum = 0;
    for (let j = i; j < N; j++) {
      sum += arr[j];
      if (sum <= M) count++;
      else break;
    }
  }
  return count;
}
console.log(solution5_4(5, 5, [1, 3, 1, 2, 3]));

• 숫자 늘려가면서 합 구하다가 합이 5를 넘어가면 while문 안에서 5이하가 될때까지 시작 포인트가 밀려난다.

사실 이 문제는 강의를 들어도 완벽히 이해가 되지 않아서 나중에 다시 돌아봐야 할 것 같다.

 

 

Section5_5번: 최대 매출 (슬라이드 윈도우)

function solution5_5(N: number, K: number, arr: number[]): number {
  let maxSum = 0;
  for (let i = 0; i <= N - K; i++) {
    let sumThreeDay = arr[i] + arr[i + 1] + arr[i + 2];
    if (maxSum < sumThreeDay) maxSum = sumThreeDay;
  }
  return maxSum;
}
console.log(solution5_5(10, 3, [12, 15, 11, 20, 25, 10, 20, 19, 13, 15]));