[20211028]알고리즘 풀이

공통원소 구하기
 A, B 두 개의 집합이 주어지면 두 집합의 공통 원소를 추출하여 오름차순으로 출력하는 프로 그램을 작성하세요. ▣ 입력설명
첫 번째 줄에 집합 A의 크기 N(1<=N<=30,000)이 주어집니다.
두 번째 줄에 N개의 원소가 주어집니다. 원소가 중복되어 주어지지 않습니다.
세 번째 줄에 집합 B의 크기 M(1<=M<=30,000)이 주어집니다.
네 번째 줄에 M개의 원소가 주어집니다. 원소가 중복되어 주어지지 않습니다.
각 집합의 원소는 1,000,000,000이하의 자연수입니다.
▣ 출력설명
 두 집합의 공통원소를 오름차순 정렬하여 출력합니다.
▣ 입력예제 1
5 1 3 9 5 2 5 3 2 5 7 8
▣ 출력예제 1
2 3 5

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

let a=[1, 3, 9, 5, 2];
let b=[3, 2, 5, 7, 8];
console.log(solution(a, b));

위의 방식으로 풀 수도 있지만 two-pointers방식으로 풀 수도 있다. 시간복잡도 측면에서 더 효율적이다.

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

 

연속 부분수열 1
 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을 넘지 않는 자연수이다.
▣ 출력설명
첫째 줄에 경우의 수를 출력한다.
▣ 입력예제 1
8 6 1 2 1 3 1 1 1 2
▣ 출력예제 1
3

function solution(m, arr){
  let answer=0, sum = 0;
  let p1=p2=0
  while (p1 < arr.length) {
    if (sum < 6) sum += arr[p2++]
    else if (sum === 6) {
      sum = 0
      answer++
      p2 = ++p1
    } else {
      sum = 0
      p2 = ++p1
    }
  }
  return answer;
}

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

function solution(m, arr){
  let answer=0, lt=0, sum=0, rt=0;
  while (lt < 8 && rt < 8) {
    if (sum < 6) {
    	sum += arr[rt++]
    } else if (sum > 6) {
    	sum -= arr[lt++]
    } else {
      answer++
      sum -= arr[lt++]
    }
  }        
  return answer;
}

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