교육과정 설계
현수는 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“를 출력하는 프로그램을 작성하세요.
나의 풀이
function solution(need, plan) {
let answer = 'YES';
let idx = [];
for (let i = 0; i < need.length; i++) {
if (plan.indexOf(need[i]) == -1) return 'NO';
idx.push(plan.indexOf(need[i]));
if (i != 0) {
if (idx[i - 1] > idx[i]) return 'NO';
}
}
return answer;
}정답 풀이
function solution(need, plan){
let answer="YES";
let queue=need.split('');
for(let x of plan){
if(queue.includes(x)){
if(x!==queue.shift()) return "NO";
}
}
if(queue.length>0) return "NO";
return answer;
}해결 방법
현수의 교육과정이 필수과목 순서를 지키지 않은 경우는 다음 두가지이다.
- 필수과목 중 수강하지 않은 과목이 있는 경우
- 선수과목을 이수하기 전에 다른 과목을 먼저 수강한 경우
스택과 큐를 사용하는 문제라는 것을 사전에 알고 있었지만, 정답 풀이와 나의 풀이 사이에 가독성 자체에는 큰 차이가 없었다. 또한 필수과목 need의 길이만큼 교육과정인 plan을 한글자씩 한번 순회하는 것이 최대 복잡도라는 것도 동일했다. 하지만, 나의 풀이의 경우는 plan만큼 반복하는 for문에서 2번째 반복부터 즉, if(i!=0)을 만족하는 경우에 선수과목의 이수 이후에 이수를 하는지를 확인하는데, 정답 풀이의 경우, 첫번째 plan이 필수과목에 포함되는 경우 선수과목을 이수하기 전에 다른 과목을 먼저 수강했는지 여부를 need를 Queue의 형태로 저장한 array queue를 dequeue와 같은 기능을 하는 shift()를 통해 확인하고, 같지 않다면 선수과목 순서대로 수강하지 않았다는 의미이기 때문에 바로 'NO'를 return하도록 했다. 따라서 나의 풀이는
- 선수과목을 이수하기 전에 다른 과목을 먼저 수강한 경우
중에서도 현수의 교육과정 중 첫번째 과목이 두번째 필수과목이라 선수과목을 수강하지 않은 상태일 때, 다음 필수과목이 등장할 때까지 'NO'를 return하지 않지만, 정답 풀이는 첫번째 필수과목이 등장했을때 필수과목의 첫번째 선수과목을 shift()하고 그 둘이 서로 다르다는 것을 통해 'NO'를 return하고 반복을 멈춘다는 점에서 나의 답보다 더 효율적인 답안이다.
Array.prototype.includes()
Array의 내부에 인자가 존재하는지를 true혹은 false로 return하며, 두번째 인자로서 정수 i를 준다면, Array의 i번째 값부터 확인하여 첫번째 인자를 포함하는지 여부를 true혹은 false로 return한다. 두번째 인자가 없는 경우 기본값은 0이다.
cf. String.prototype.includes()도 같은 기능을 한다.
