[프로그래머스] 스킬트리

https://programmers.co.kr/learn/courses/30/lessons/49993

코딩테스트 연습 - 스킬트리

풀이과정

올바른 과정으로 스킬을 찍혔는지 확인하는 문제였다.

A -> B -> C를 과정으로 스킬을 배워야한다고 가정하면, A -> C -> B는 틀린 스킬 트리가 된다.

A -> B -> C의 순서는 필수조건인 셈이다. 하지만 아래처럼 중간에 다른 스킬이 들어가도 상관없다.

A -> E -> B -> Z -> C 처럼 E와 Z가 들어가도 OK!

 

예외사항은 3가지 경우가 생각이 났다.

 

1. A, B, C를 안배운 경우

2. 필수 순서는 맞지만 뒤에 몇가지를 빼먹은 경우

3. 순서가 어긎난 경우

 

1번의 경우 현재 스킬트리 문자열에서 필수 스킬이 하나라도 포함되지 않으면 된다. (indexOf가 모두 -1이 나오면 된다.)

 

2번의 경우 필수스킬을 찾는 도중 포함되지 않는 것이 발견 된 경우 나머지 문자열에서 필수 스킬이 포함되어 있지 않으면 된다. (필수스킬 순서로 A -> B -> Z -> F -> G와 같이 C가 없는 경우)

 

3번의 경우 애초에 B -> A -> C 인 경우이다. (indexOf를 이전 indexOf값과 비교하면 된다.)

 

 

소스코드

function solution(skill, skill_trees) {
	var answer = 0;
	for (var i = 0; i < skill_trees.length; i++) {
		var prev = skill_trees[i].indexOf(skill[0]);
		var correctSkillOrder = true;
		if (prev !== -1) {
			for (var j = 1; j < skill.length; j++) {
				var cur = skill_trees[i].indexOf(skill[j]);
				if (cur === -1) {
					for (var k = j + 1; k < skill.length; k++) {
						if (skill_trees[i].indexOf(skill[k]) !== -1) {
							correctSkillOrder = false;
							break;
						}
					}
					break;
				}
				else {
					if (prev > cur) {
						correctSkillOrder = false;
						break;
					}
					prev = cur;
				}
			}
		}
		else {
			for (var j = 1; j < skill.length; j++) {
				if (skill_trees[i].indexOf(skill[j]) !== -1) {
					correctSkillOrder = false;
					break;
				}
			}
		}
		if (correctSkillOrder) {
			answer++;
		}
	}
	return answer;
}