[알고리즘] 효율성(투포인터 알고리즘, 슬라이딩윈도우, 해쉬)

먼지·2022년 10월 15일

알고리즘 코딩테스트 연습

목록 보기

10/10

1. 두 배열 합치기(Two Pointers Algorithm)

오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 프로그램
을 작성하세요.

✏ 입력 설명
첫 번째 줄에 첫 번째 배열의 크기 N(1<=N<=100)이 주어집니다.
두 번째 줄에 N개의 배열 원소가 오름차순으로 주어집니다.
세 번째 줄에 두 번째 배열의 크기 M(1<=M<=100)이 주어집니다.
네 번째 줄에 M개의 배열 원소가 오름차순으로 주어집니다.
각 리스트의 원소는 int형 변수의 크기를 넘지 않습니다.

✏ 출력 설명
오름차순으로 정렬된 배열을 출력합니다

function solution1(arr1, arr2) {
  // 일단 sort를 하면 NlogN의 시간복잡도
  return [...arr1, ...arr2].sort();
}

// 나중에 병합정렬을 배우기 위해서
function solution2(arr1, arr2) {
  let answer = [];
  let p1 = 0,
    p2 = 0;
  // 두개의포인트를잡음 => two pointers algorithm => O(n + m) 시간 복잡도
  let n = arr1.length;
  let m = arr2.length;
  while (p1 < n && p2 < m) {
    if (arr1[p1] <= arr2[p2]) answer.push(arr1[p1++]);
    else answer.push(arr2[p2++]);
  }
  while (p1 < n) answer.push(arr1[p1++]);
  while (p2 < m) answer.push(arr2[p2++]);
  return answer;
}

let a = [1, 3, 5];
let b = [2, 3, 6, 7, 9];

console.log(solution1(a, b)); // [ 1, 2, 3, 3, 5, 6, 7, 9 ]
console.log(solution2(a, b)); // [ 1, 2, 3, 3, 5, 6, 7, 9 ]

투포인터 알고리즘을 몰라서 당연히 문제를 보자마자 sort method를 떠올렸다. 이번 문제는 강의를 보고 투포인트 알고리즘이 뭔지 배웠고, 증감 연산자를 오랜만에 써서 조금 헷갈렸다.. 그리고 sort가 NlogN의 시간 복잡도라는데 아직 빅 오와 시간 복잡도를 잘 몰라서 배워야겠다 😬

2. 공통원소 구하기(Two Pointers Algorithm)

A, B 두 개의 집합이 주어지면 두 집합의 공통 원소를 추출하여 오름차순으로 출력하는 프로
그램을 작성하세요.

✏ 입력 설명
첫 번째 줄에 집합 A의 크기 N(1<=N<=30,000)이 주어집니다.
두 번째 줄에 N개의 원소가 주어집니다. 원소가 중복되어 주어지지 않습니다.
세 번째 줄에 집합 B의 크기 M(1<=M<=30,000)이 주어집니다.
네 번째 줄에 M개의 원소가 주어집니다. 원소가 중복되어 주어지지 않습니다.
각 집합의 원소는 1,000,000,000이하의 자연수입니다.

✏ 출력 설명
두 집합의 공통원소를 오름차순 정렬하여 출력합니다.

// sort - O(nlogn)
function solution1(arr1, arr2) {
  let answer = [];
  for (let v of arr1) {
    if (arr2.includes(v)) answer.push(v);
  }
  // 정렬 기준 콜백 함수를 전달하지 않고 그냥 sort만 쓰면
  // 기본적으로 배열의 원소들을 문자열로 변환한 후 정렬함
  return answer.sort((a, b) => a - b);
}

function solution2(arr1, arr2) {
  let answer = [];
  arr1.sort((a, b) => a - b);
  arr2.sort((a, b) => a - b);
  let p1 = (p2 = 0);
  while (p1 < arr1.length && p2 < arr2.length) {
    if (arr1[p1] == arr2[p2]) {
      answer.push(arr1[p1++]);
      p2++;
    } //
    else if (arr1[p1] < arr2[p2]) p1++;
    else p2++;
  }
  return answer;
}

console.log(solution1([1, 3, 9, 5, 2], [3, 2, 5, 7, 8])); // [ 2, 3, 5 ]
console.log(solution2([1, 3, 9, 5, 2], [3, 2, 5, 7, 8])); // [ 2, 3, 5 ]

3. 연속 부분수열 1(Two Pointers Algorithm)

N개의 수로 이루어진 수열이 주어집니다.
이 수열에서 연속부분수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하는 프로그램을
작성하세요.
만약 N=8, M=6이고 수열이 다음과 같다면
1 2 1 3 1 1 1 2
합이 6이 되는 연속부분수열은 {2, 1, 3}, {1, 3, 1, 1}, {3, 1, 1, 1}로 총 3가지입니다.

✏ 입력 설명
첫째 줄에 N(1≤N≤100,000), M(1≤M≤100,000,000)이 주어진다.
수열의 원소값은 1,000을 넘지 않는 자연수이다.

✏ 출력 설명
첫째 줄에 경우의 수를 출력한다

// m보다 작으면 rt증가하면서 더하고, 크거나 같으면 lt가 증가하면서 빼기
function solution(m, arr) {
  let answer = 0,
    lt = 0,
    sum = 0;
  for (let rt = 0; rt < arr.length; rt++) {
    sum += arr[rt];
    if (sum === m) answer++;
    while (sum >= m) {
      sum -= arr[lt++];
      if (sum === m) answer++;
    }
  }
  return answer;
}

let arr = [1, 2, 1, 3, 1, 1, 1, 2];
console.log(solution(6, arr)); // 3

4. 연속 부분수열 2(Two Pointers Algorithm)

N개의 수로 이루어진 수열이 주어집니다.
이 수열에서 연속부분수열의 합이 특정숫자 M이하가 되는 경우가 몇 번 있는지 구하는 프로그
램을 작성하세요.
만약 N=5, M=5이고 수열이 다음과 같다면
1 3 1 2 3
합이 5이하가 되는 연속부분수열은 {1}, {3}, {1}, {2}, {3}, {1, 3}, {3, 1}, {1, 2}, {2, 3},
{1, 3, 1}로 총 10가지입니다.

✏ 입력 설명
첫째 줄에 N(1≤N≤100,000), M(1≤M≤100,000,000)이 주어진다.
수열의 원소값은 1,000을 넘지 않는 자연수이다.

✏ 출력 설명
첫째 줄에 경우의 수를 출력한다.

// 뺴놓고도카운팅
function solution(m, arr) {
  let answer = 0,
    lt = 0,
    sum = 0;

  for (let rt = 0; rt < arr.length; rt++) {
    sum += arr[rt];
    while (sum > m) {
      sum -= arr[lt++];
    }
    answer += rt - lt + 1;
  }

  return answer;
}

function solution1(m, arr) {
  let answer = 0,
    lt = 0,
    rt = 0,
    sum = arr[rt];

  while (rt < arr.length) {
    if (sum <= m) {
      answer += rt - lt + 1;
      rt++;
      sum += arr[rt];
    } else {
      sum -= arr[lt];
      lt++;
    }
  }

  return answer;
}

let arr = [1, 3, 1, 2, 3];
console.log(solution(5, arr)); // 10
console.log(solution1(5, arr)); // 10

5. 최대 매출(Sliding Window)

현수의 아빠는 제과점을 운영합니다. 현수 아빠는 현수에게 N일 동안의 매출기록을 주고 연속
된 K일 동안의 최대 매출액이 얼마인지 구하라고 했습니다.
만약 N=10이고 10일 간의 매출기록이 아래와 같습니다. 이때 K=3이면
12 15 11 20 25 10 20 19 13 15
연속된 3일간의 최대 매출액은 11+20+25=56만원입니다.
여러분이 현수를 도와주세요.

✏ 입력 설명
첫 줄에 N(5<=N<=100,000)과 K(2<=K<=N)가 주어집니다.
두 번째 줄에 N개의 숫자열이 주어집니다. 각 숫자는 500이하의 음이 아닌 정수입니다.

✏ 출력 설명
첫 줄에 최대 매출액을 출력합니다.

// 슬라이딩 윈도우 기법
// 창문을 그리고(k칸) 옆으로 한 칸씩 미는 것
// [12 15 11] 20 25 ...
// => 38
//
// 12 [15 11 20] 25 ...
// 38 + 20 - 12 => 46
//
// for 문에서 i 가 증가하면서 가니까, sum + arr[i] - arr[i-k]
// 창문에 보이는 숫자 더하면서 옆으로 밀고 가기
function solution(k, arr) {
  let answer = (sum = 0);
  for (let i = 0; i < k; i++) sum += arr[i];
  answer = sum;

  for (let i = k; i < arr.length; i++) {
    sum += arr[i] - arr[i - k];
    answer = Math.max(answer, sum);
  }

  return answer;
}

const arr = [12, 15, 11, 20, 25, 10, 20, 19, 13, 15];
console.log(solution(3, arr)); // 56

6. 학급 회장(Hash Map)

학급 회장을 뽑는데 후보로 기호 A, B, C, D, E 후보가 등록을 했습니다.
투표용지에는 반 학생들이 자기가 선택한 후보의 기호(알파벳)가 쓰여져 있으며 선생님은 그
기호를 발표하고 있습니다.
선생님의 발표가 끝난 후 어떤 기호의 후보가 학급 회장이 되었는지 출력하는 프로그램을 작
성하세요. 반드시 한 명의 학급회장이 선출되도록 투표결과가 나왔다고 가정합니다.

✏ 입력 설명
첫 줄에는 반 학생수 N(5<=N<=50)이 주어집니다.
두 번째 줄에 N개의 투표용지에 쓰여져 있던 각 후보의 기호가 선생님이 발표한 순서대로
문자열로 입력됩니다.

✏ 출력 설명
학급 회장으로 선택된 기호를 출력합니다.

// Map은 key와 value가 한 쌍으로 된 객체
// let sH = new Map(); // string hash
//      B   A   ...
// sH | 1 | 1 | ... |
//
// sH.set('B', 1) B 문자열의 키를 갖는 값을 1로 세팅
// 기존 키에 값이 없으면 만들고, 있으면 get 해서 + 1

function solution(str) {
  let answer;
  let sH = new Map();
  let max = Number.MIN_SAFE_INTEGER;

  for (let s of str) {
    if (sH.has(s)) {
      sH.set(s, sH.get(s) + 1);
    } else {
      sH.set(s, 1);
    }
  }

  for (let [key, val] of sH) {
    // console.log(key, ':', val);
    if (val > max) {
      max = val;
      answer = key;
    }
  }

  return answer;
}

let str = 'BACBACCACCBDEDE';
console.log(solution(str)); // C

7. 아나그램(Hash Map)

Anagram이란 두 문자열이 알파벳의 나열 순서를 다르지만 그 구성이 일치하면 두 단어는 아
나그램이라고 합니다.
예를 들면 AbaAeCe 와 baeeACA 는 알파벳을 나열 순서는 다르지만 그 구성을 살펴보면
A(2), a(1), b(1), C(1), e(2)로 알파벳과 그 개수가 모두 일치합니다. 즉 어느 한 단어를 재
배열하면 상대편 단어가 될 수 있는 것을 아나그램이라 합니다.
길이가 같은 두 개의 단어가 주어지면 두 단어가 아나그램인지 판별하는 프로그램을 작성하세
요. 아나그램 판별시 대소문자가 구분됩니다.

✏ 입력 설명
첫 줄에 첫 번째 단어가 입력되고, 두 번째 줄에 두 번째 단어가 입력됩니다.
단어의 길이는 100을 넘지 않습니다.

✏ 출력 설명
두 단어가 아나그램이면 “YES"를 출력하고, 아니면 ”NO"를 출력합니다.

function solution(str1, str2) {
  let answer;

  let map1 = new Map();
  for (let s of str1) {
    if (map1.has(s)) map1.set(s, map1.get(s) + 1);
    else map1.set(s, 1);
  }

  let map2 = new Map();
  for (let s of str2) {
    if (map2.has(s)) map2.set(s, map2.get(s) + 1);
    else map2.set(s, 1);
  }

  for (let s of str1) {
    if (map1.get(s) === map2.get(s)) answer = 'YES';
    else answer = 'NO';
  }

  return answer;
}

function compareMaps(map1, map2) {
  if (map1.size !== map2.size) return false;
  for (let [key, val] of map1) {
    if (!map2.has(key) || map2.get(key) !== val) return false;
  }
  return true;
}
function solution1(s, t) {
  let answer = 0;
  let tH = new Map();
  let sH = new Map();
  for (let x of t) {
    if (tH.has(x)) tH.set(x, tH.get(x) + 1);
    else tH.set(x, 1);
  }
  let len = t.length - 1;
  for (let i = 0; i < len; i++) {
    if (sH.has(s[i])) sH.set(s[i], sH.get(s[i]) + 1);
    else sH.set(s[i], 1);
  }
  let lt = 0;
  for (let rt = len; rt < s.length; rt++) {
    if (sH.has(s[rt])) sH.set(s[rt], sH.get(s[rt]) + 1);
    else sH.set(s[rt], 1);
    if (compareMaps(sH, tH)) answer++;
    sH.set(s[lt], sH.get(s[lt]) - 1);
    if (sH.get(s[lt]) === 0) sH.delete(s[lt]);
    lt++;
  }
  return answer > 0 ? 'YES' : 'NO';
}

const s1 = 'AbaAeCe';
const s2 = 'baeeACA';
console.log(solution(s1, s2)); // YES
console.log(solution1(s1, s2)); // YES
const str1 = 'abaCC';
const str2 = 'Caaab';
console.log(solution(str1, str2)); // NO
console.log(solution1(str1, str2)); // NO
let a = 'AABBCC';
let b = 'EEFFGG';
console.log(solution(a, b)); // NO
console.log(solution1(a, b)); // NO