[알고리즘] 부분집합 찾기

ㅜㅜ·2022년 11월 1일
1

알고래즘

목록 보기
1/20
post-thumbnail

배열인 base와 sample을 인자로 입력 받아 sample이 base의 부분집합인지 여부를 리턴하는 문제

(아래 스니펫들은 문제 풀이 중 부분만 담고 있음)

문제 풀이 순서

  1. 오름차순으로 정렬하기
    : 뭔가를 비교하는 문제에서 의외로 정렬을 하는 경우가 많은데, 정렬을 하게 되면 아무래도 비교를 하는 가짓수가 많이 줄기 때문인 것 같다. (시간 복잡도)
base.sort((a-b) => a-b)
sample.sort((a-b) => a-b)
  1. 새로운 함수를 만들어 줌
    : 새로운 함수가 하는 일은 item과 arr, 그리고 from(시작부분)을 받아서 받은 item과 arr에서 from부터 arr.length 전까지의 요소들 중 같은 값이 있는지를 찾는 반복문을 담고 있다.
    왜 하필 새로운 함수를 만들어야만 했는가에 대해 고민해봤는데, 결론적으로 이 함수는 이중 for문의 내부 for문의 역할과 비슷하다는 것을 알게 되었고...
    새로운 함수 다음에 나오는 for문이 하나 더 있는데, 그 for문은 from을 정해주는 바깥쪽 for문 역할을 했다.
const findInSortedArr= (item,arr,from) => {
    for (let i = from; i < arr.length; i++) {
      if (item === arr[i]) return i;
      else if (item < arr[i]) return -1;
    }
    return -1;
  }

let baseIdx = 0;
  for (let i = 0; i < sample.length; i++) {
    baseIdx = findItemInSortedArr(sample[i], base, baseIdx);
    if (baseIdx === -1) return false;
  }
  return true;

사실 순서로는 아래쪽 식부터 시작되고, 위의 함수에 baseIdx 값 등이 전달되면 비교 후,
같은 값이 있다면 해당 값이 있는 index가 baseIdx로 전달됨.
만약 같은 값이 아니면서 샘플의 요소 값이 base의 요소 값보다 작게 되면 그 이후로는 같은 값이 있을 가능성이 없어지므로 (정렬을 했기 때문에) 바로 -1을 리턴하고, -1이 리턴되면 false가 리턴된다.

*이중 반복문으로 만들어보려고 했는데 내가 틀리게 작성했는지 제대로 결과가 나오지 않았음.
이후에 추가적으로 학습해보고 더 추가할 점 있으면 더 추가할 예정.

profile
다시 일어나는 중

0개의 댓글