[Algorythm][JS][Queue] 교육과정 설계

문제

현수는 1년 과정의 수업계획을 짜야 합니다.
수업중에는 필수과목이 있습니다. 이 필수과목은 반드시 이수해야 하며, 그 순서도 정해져 있습니다.
만약 총 과목이 A, B, C, D, E, F, G가 있고, 여기서 필수과목이 CBA로 주어지면
필수과목은 C, B, A과목이며 이 순서대로 꼭 수업계획을 짜야 합니다.
여기서 순서란 B과목은 C과목을 이수한 후에 들어야 하고, A과목은 C와 B를 이수한 후에 들어야 한다는 것입니다.
현수가 C, B, D, A, G, E로 수업계획을 짜면 제대로 된 설계이지만
C, G, E, A, D, B 순서로 짰다면 잘 못 설계된 수업계획이 됩니다.
수업계획은 그 순서대로 앞에 수업이 이수되면 다음 수업을 시작하다는 것으로 해석합니다.
수업계획서상의 각 과목은 무조건 이수된다고 가정합니다.
필수과목순서가 주어지면 현수가 짠 N개의 수업설계가 잘된 것이면 “YES",
잘못된 것이면 ”NO“를 출력하는 프로그램을 작성하세요.

* 입력
첫 줄에 한 줄에 필수과목의 순서가 주어집니다. 모든 과목은 영문 대문자입니다.
두 번 째 줄부터 현수가 짠 수업설계가 주어집니다.(수업설계의 길이는 30이하이다)

* 출력
첫 줄에 수업설계가 잘된 것이면 “YES", 잘못된 것이면 ”NO“를 출력합니다.

▷ 입력 예시
CBA
CBDAGE

▷ 출력 예시
YES_

풀이

풀이1

필수과정을 담은 문자열을 배열화 해 queue로 사용했다.
설계한 교육과정을 돌면서 queue의 맨 앞요소와 같을 경우 queue의 맨 앞 요소를 삭제 해준다.
해당 과목을 이수했다고 생각하면 된다.
이 과목을 이수한 다음에 맨앞에 오는 과목은 다음으로 이수해야 하는 과목이다.
만약 이 다음 필수과목이 설계한 교육과정에서 순서가 다르다면 삭제되지 않는다.

function solution(necs, classes) {
  const necsQueue = necs.split('');
  const classesArr = classes.split('');
  
  for(cl of classesArr) {
    if(necsQueue[0] === cl) {
      necsQueue.shift();
    }
  }
  
   return necsQueue.length ? "NO" : "YES";
}

그런데.. 이 풀이는 교육과정을 모두 돌아 검사하기 전까지는 종료되지않는다는 단점이 있다.

풀이2

function solution(necs, classes) {
  let answer = "YES";
  let necsQueue = necs.split('');
  for(let cl of classes) {
  	if(necsQueue.includes(cl) {
    	if(cl !== necsQueue.shift()) {
    		return "NO";
    	}   
    }
  if(necsQueue.length > 0) return "NO";
  return answer;
}

해당 수업을 포함할 경우에 필수과목 순서에 맞게 교육과정이 설계가 되어 있지않다면 바로 리턴해주기 때문에 교육과정의 길이가 길어져도 연산시간을 아낄수있다.
(필수과목이 아닌 교육과정의 과목은 그대로 넘어간다.)

Reference

• 인프런 - 자바스크립트 알고리즘 문제풀이 (김태원)