출처
해당 게시글은 [Java] 어서와! 자료구조 알고리즘은 처음이지?https://programmers.co.kr/learn/courses/13577를 간략히 요약한 게시글이며 모든 출처는 해당강의에 있습니다
문제
문제분석
순서에 상관 있는 스킬들과 상관 없는 스킬들이 합쳐져 있는 스킬트리에서 순서에 상관 있는 스킬들 간의 순서가 옳바른지 확인하는 문제입니다.
풀이
나의 풀이
class Solution {
public int solution(String skill, String[] skill_trees) {
//올바른 스킬트리 수
int count = 0;
//스킬트리 하나씩 비교
for(String skill_tree : skill_trees){
//순서에 상관 없는 스킬들 전부제거
skill_tree = skill_tree.replaceAll("[^"+skill+"]","");
//순서에 상관 있는 스킬들이 skill과 같으면 +1
if(skill.startsWith(skill_tree)) count++;
}
//올바른 스킬 순서 리턴
return count;
}
}이전에 풀어봤었던 문제들과 유형이 비슷하여 어렵지 않게 구현할 수 있었습니다. 아주 옛날에 비슷한 문제를 풀었을때 문자열의 한 문자씩 비교분석 하며 풀었던 기억도 조금 남습니다.
- 스킬트리에서 순서에 상관 없는 스킬들을 제거하고
- 순서에 상관 있는 스킬들이
skill순서에 맞다면 갯수 +1
2단계로 비교적 짧고 간단하게 갯수를 셀 수 있었던 이유는 String.replaceAll("old","new") API로 old는 정규표현식으로 "[^skill]", new는 빈 문자열 ""을 지정하여 skill에 없는 문자 = 순서에 상관 없는 스킬들을 모두 제거하였기 때문에 순서에 상관 있는 문자들만 간단히 비교할 수 있었습니다.
skill_tree에는 skill이 모두 있지 않아도 되지만 순서는 엄격히 지켜져야 하므로 skill = "CBD"이고 skill_tree = "C", "CB" 또한 가능합니다.
강의의 풀이
나의 풀이와 마찬가지로 .replaceAll("old","new")를 이용하여 순서에 상관 없는 스킬들을 제거하는건 동일하였으나 리펙토링 하여 스트림으로 구현 하였습니다.
import java.util.*;
class Solution {
public int solution(String skill, String[] skill_trees) {
return (int) Arrays.stream(skill_trees)
.map(s -> s.replaceALL("[^"+skill+"]",""))
.filter(s -> skill.startsWith(s))
.count();
}
}Arrays.stream(skill_tree) : skill_tree를 스트림으로 변경합니다.
.map(s -> s.replaceALL("[^"+skill+"]","")) : 순서에 상관 없는 스킬들을 skill_tree에서 제거합니다.
.filter(s -> skill.startsWith(s)) : 순서에 상관 있는 스킬들이 skill의 순서에 맞춘 skill_tree만 추려냅니다.
.count() 남은 skill_tree의 갯수만 리턴합니다.
GitHub
