스킬트리(programers > lev2 > 문자열_String)

문제 링크

문제설명

선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.

예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다.

위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다.

선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요.

입출력 예

입출력 예 설명

• BACDE: B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트립니다.
• CBADF: 가능한 스킬트리입니다.
• AECB: 가능한 스킬트리입니다.
• BDA: B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트리입니다.

풀이

    public int solution(String skill, String[] skill_trees) {
    	char arr[] = new char[skill.length()];
    	int answer = 0;
    	
    	for(int i=0;i<skill.length(); i++)
    		arr[i] = skill.charAt(i);
    	
    	for(int i=0;i<skill_trees.length;i++) {
    		ArrayList<Character> s = new ArrayList<Character>();
    		
    		for(int j=0; j<skill_trees[i].length(); j++) {
    			for(int k=0; k<arr.length; k++) {
    				if(skill_trees[i].charAt(j) == arr[k])
    					s.add(arr[k]);
    			}
    		}
    		
    		boolean chk = false;
    		for(int j=0; j<s.size(); j++) {
    			if(arr[j] != s.get(j))
    				chk=true;
    		}
    		
    		if(chk==false) 
    			answer++;
    		
    		chk= false;
    		s.clear();
    	}
    
    	return answer;
    }

후기 (30min)

한번 풀었었음에도 불구하고… 어떻게 풀지 고민을 좀 오래했다! 전에 했던거 보니까 전에도 비슷하게 풀었던데 조오오오금 깔끔해진 정도?

이거랑 비슷한 문제가 하나 더 있었는데 기억이 안나는데.. 아무튼 그거나 이거나 한 배열의 순서가 정해져있기 때문에 걔의 idx를 기준으로 잡고 가도 되고, 이렇게 size가 정해진다면 꼼수를 부려서 그 size에 정해진 변수가 뭔지를 알아내는 식으로 풀어도 된다!

tip

1. char 배열을 쓰면 생각보다 문자열의 charAt(i)를 쉽게 사용할 수 있다!! 익숙해지자!