• 배열 base, sample가 있다고 가정하면 sample가 base의 부분집합인지 여부를 확인해라

시간복잡도를 고려하지 않은 코드 1

• sample의 0번째 인덱스, base의 0번째 인덱스부터 탐색하여 sample[i] === base[j]인 경우 result를 true로 세팅해주는 코드이다.
• base와 sample이 같은순서로 정렬되어있지 않기 때문에 탐색하는데 시간이 오래걸린다.

function isSubset(base, sample) {
	// 여부를 리턴 할 변수를 하나 만들어주는데 기본값은 false로 세팅한다.
	let result = false;

	// 이중포문을 돌려서 base와 sample의 요소가 같은지 확인하고 같으면 true 아니면 false를 result에 할당한다.
	for(let i=0; i<sample.length; i++) {
		for(let j=0; j<base.length; j++) {
			//sample 요소랑 base요소가 같은지 확인한다.
			if(sample[i] === base[j]) {
				result = true;
				break;
			} else {
					result = false;
				}
		}
	}
	// result를 리턴한다.
	return result;
}

시간복잡도를 고려하지 않은 코드2 (every 메서드 사용)

• every메서드를 사용하여 base에 sample의 요소가 있는지 확인하고 있으면 true를 리턴한다.
• 코드는 간단하지만 역시 base와 sample이 같은 순서로 정렬 되어있지 않은 경우도 있고 전체 탐색을 하기 때문에 시간이 오래걸린다. 시간복잡도는 O(m * n)이다

function isSubset(base, sample) {
	return sample.every(el => {
		if(base.includes(el)) {
			return true;
		} else {
				return false;
			}
	});
}

시간복잡도를 고려한 코드1

• 이중 for문을 사용하되 j를 0번째 인덱스부터 하는것이 아닌 i번째 인덱스부터 탐색한다.
  • i번째 인덱스부터 탐색하기 때문에 base, sample은 같은 순서로 정렬되어야한다.
• j=i번째 인덱스부터 탐색하기 때문에 정렬이 되어있지 않아 base와 sample의 순서가 같지 않은 경우 에러가 발생한다. 따라서 오름차순으로 정렬해준 다음 이중포문을 돌린다.
• 하지만 이 코드 또한 **시간복잡도는 O(n^2)**이므로 효율적이지는 못하다고 할 수 있다.

function isSubset(base, sample) {
	// true, false를 리턴 할 변수를 하나 만들어주고 false로 세팅해준다.
	let result = false;

	// base와 sample을 오름차순으로 정렬해준다.
	base.sort((a, b) => a-b);
	sample.sort((a, b) => a-b);

	// 이중포문을 돌려서 base와 sample의 요소가 같은지 확인하고 같으면 true 아니면 false를 result에 할당한다.
	for(let i=0; i<sample.length; i++) {
		for(let j=i; j<base.length; j++) {
			//sample 요소랑 base요소가 같은지 확인한다.
			if(sample[i] === base[j]) {
				result = true;
				break;
			} else {
					result = false;
				}
		}
	}
	// result를 리턴한다.
	return result;
}