[JS] 코딩 테스트 문제 : 공통원소구하기

문제 : 공통원소구하기

문제 설명

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

 

▣ 입력설명

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

 

▣ 출력설명

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

 

▣ 입력예제 1

[1, 3, 9, 5, 2]
[3, 2, 5, 7, 8]

 

▣ 출력예제 1

2 3 5

내코드

 

function solution(arr1, arr2) {
  let answer = [];
  let sortArr1 = arr1.sort((a, b) => a - b);
  let sortArr2 = arr2.sort((a, b) => a - b);
  let arr1Index = 0;
  let arr2Index = 0;
  let currentValue;

  for (let i = 0; i < sortArr1.length + sortArr2.length; i++) {
    // sortArr1[arr1Index] 이 더 작으면 arr1Index 1 증가
    if (sortArr1[arr1Index] < sortArr2[arr2Index]) {
      arr1Index++;
    }
    // sortArr2[arr2Index] 이 더 작으면 arr2Index 1 증가
    else if (sortArr1[arr1Index] > sortArr2[arr2Index]) {
      arr2Index++;
    }
    // sortArr1[arr1Index] 와 sortArr2[arr2Index] 값이 동일하면 배열에 저장
    else {
      answer.push(sortArr1[arr1Index]);
      arr1Index++;
      arr2Index++;
    }

    // 한쪽 배열이라도 비워진 경우
    if (
      sortArr1[arr1Index] === undefined ||
      sortArr2[arr2Index] === undefined
    )
      break;
  }
  return answer;
}

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

풀이

 

1. 각각의 배열을 sort 메서드로 오름차순으로 정렬
2. 정렬된 배열을 투포인터로 비교해
3. 이미 정렬된 두 배열에 각각의 인덱스값 0 을 지정 (투 포인트 개념)
4. 각 배열의 index 번의 숫자와 비교해 더 작은 숫자값은 저장하고 그 배열의 index 를 증가시킨다.
5. 같아지는 경우만 배열에 저장

보완할 수 있는 부분

 

// 기존코드
for (let  i  =  0; i  <  sortArr1.length +  sortArr2.length; i++) {
  ...
}

// 보완코드
 while(p1<arr1.length && p2<arr2.length){
  ...
 }

 

기존 코드에서는 1번 2번 배열 값 만큼 for 문을 돌렸다면 while 문으로 1번 2번 배열 중 index 가 최대치만큼 이동한 경우 다음 while 문에서 나머지 내용 다 넣어주고 마친다. (좀 더 간결)

---

참고

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4/dashboard