[Programmers] Level 2 : 스킬트리

프로그래머스

간단하게 해결할 수 있는 문제지만, java로 알고리즘 문제를 많이 안풀어봐서 조금 버벅였다.

문제를 쉽게 풀어내기 위해 어떤 순서로 해결할지 생각해봤다.

1. 우선 set으로 주어진 skill 트리에 있는 문자열들을 전부 관리한다. 그다음 skill_trees에 있는 문자열을 하나씩 꺼내 skill에 들어있는 문자열만 포함하는 문자열을 만들어줬다.

2. 올바른 skill_tree 가 되기 위해서는 순서가 무조건 정해진대로 되어야 한다. 그래서 주어진 스킬의 순서가 [1, 2, 3, 4, 5]라고 할때, [1] [1, 2] [1, 2, 3] [1, 2, 3, 4] [1, 2, 3, 4, 5] 이런 순서인 애들을 찾아야 한다. 그래서 각 스킬의 위치를 map으로 관리했다.

3. 1에서 얻은 문자열을 쭉 돌면서 모든 문자열이 map에 저장된 위치와 일치하는지 확인하고 모두 만족한다면 올바른 스킬, 하나라도 만족하지 않으면 잘못된 스킬이다.

 

 

import java.util.*;
import java.lang.Math.*;

class Solution {
    private Set<Character> s = new HashSet<>();
    private Map<Character, Integer> mp = new HashMap<>();
    
    public int solution(String skill, String[] skill_trees) {
        int answer = 0;
        for(int i=0; i<skill.length(); i++) {
            mp.put(skill.charAt(i), i);
            s.add(skill.charAt(i));
        }
        for(int i=0; i<skill_trees.length; i++) {
            String tree = skill_trees[i];
            String result = "";
            for(int j=0; j<tree.length(); j++) {
                Character t = tree.charAt(j);
                if(s.contains(t)) {
                    result += t;
                }
            }
            Boolean flag = true;
            for(int j=0; j<result.length(); j++) {
                Character t = result.charAt(j);
                if (j != mp.get(t)) flag = false;
            }
            if(flag) answer++;
        }
        return answer;
    }
}

위의 코드의 시간복잡도는 O(N^2logN)이고, 제한이 널널해서 무난하게 통과한다. 하지만 코드가 맘에 안든다. 문법이 안익숙해서 너무 무지성으로 푼 느낌이다. 자바의 문법을 좀더 활용한 코드는 아래와 같다.

import java.util.*;
import java.lang.Math.*;

class Solution {
    
    public int solution(String skill, String[] skill_trees) {
        int answer = 0;
        for(String skill_tree : skill_trees) {
            String result = "";
            for(int i=0; i<skill_tree.length(); i++) {
                String s = skill_tree.substring(i, i+1);
                if(skill.contains(s)) result += s;
            }
            if (skill.indexOf(result) == 0) answer++;
        }
        return answer;
    }
}

Set과 Map을 사용하지 않아도 되고, contains, indexOf로 해결할 수 있다. 시간복잡도는 O(N^3)으로 증가하긴 했지만 메모리, 가독성, 코드의 복잡성에서 개선점을 찾을 수 있다.