프로그래머스 - 스킬트리

해당 알고리즘 자료는 제가 직접 푼 것도 있지만 다른 분들의 풀이과의 비교를 통해 더 나은 알고리즘을 공부하기 위해 정리한 것들입니다.

프로그래머스 - 스킬트리

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

풀이 1. (초급) - 전체 갯수에서 해당되지 않은 스킬을 제거

class Solution {
   public int solution(String skill, String[] skill_trees) {
	int answer = skill_trees.length; // 전체 스킬 수
		for(String tree : skill_trees) {
			int idx = 0; // skill의 index
			boolean chk = false;
			for (int i = 0; i < tree.length(); i++) {
				for (int j = idx; j < skill.length(); j++) {
					if(j != idx && tree.charAt(i) == skill.charAt(j)) {
						answer--; // index을 기준으로 나중 스킬이 먼저 있으면 제외
						chk = true;
						break;
					}else if (j == idx && tree.charAt(i) == skill.charAt(j)) idx++; // index 카운트
				}
				if(chk) break;
			}
		}
	return answer;
}
}

풀이 2. (중급) - 전체 갯수에서 해당되지 않은 스킬을 index값으로 비교하여 제거

class Solution {
   public int solution(String skill, String[] skill_trees) {
	int answer = skill_trees.length;// 전체 스킬 수
	int beforeIdx = 0, currentIdx = 0;
	for (int i = 0; i < skill_trees.length; i++) {
		beforeIdx = skill_trees[i].indexOf(skill.charAt(0)); // 첫번재 스킬의 인덱스
		for (int j = 1; j < skill.length(); j++) {
			currentIdx = skill_trees[i].indexOf(skill.charAt(j)); // 현재 스킬의 인덱스
			if((beforeIdx > currentIdx && currentIdx != -1) || (beforeIdx == -1 && currentIdx != -1)) { 
            		// 현재 스킬이 존재하면서 이전 스킬이 나중에 있거나 이전 스킬이 없으면 제외
				answer--;
				break;
			} 
			beforeIdx = currentIdx; // 현재 스킬은 이전스킬이 되어 다음 스킬과 비교
		}
	}
	return answer;
}
}

풀이 3. (번외) - 반복자를 사용하여 스킬을 구별

import java.util.*;

class Solution {
    public int solution(String skill, String[] skill_trees) {
        int answer = 0;
        ArrayList<String> skillTrees = new ArrayList<String>(Arrays.asList(skill_trees));
        Iterator<String> it = skillTrees.iterator();

        while (it.hasNext()) {
            if (skill.indexOf(it.next().replaceAll("[^" + skill + "]", "")) != 0) {
            // it.next().replaceAll("[^" + skill + "]", "") : skill의 문자들을 제외한 나머지 문자들을 빈칸으로 대체한다.
                it.remove();
            }
        }
        answer = skillTrees.size();
        return answer;
    }
}