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

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

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

쉬운듯 하면서 잘 풀리지 않았던 문제.

처음 접근은 for문으로 index를 접근하려했지만 for문도 여러개이고 좋은 방법이 아닌 것 같고

다른 아이디어가 따오르지 않아 다른 블로그를 참조했다.

여러 해결방법이 있어보이지만 그나마 간단한 해결방법을 참조하였다.

 

1)

public int solution(String skill, String[] skill_trees) {
        int answer = 0;
        
        for(int i=0; i<skill_trees.length; i++) {
			if(isPossible(skill, skill_trees[i])) {
				answer++;
			}
        }
        
        return answer;
    }
	
	public boolean isPossible(String skill, String skillTree) {
		boolean possible = false;
		String skills = skillTree;
		for(int i=0; i<skillTree.length(); i++) {
			String s = String.valueOf(skillTree.charAt(i));
			if(!skill.contains(s)) {
				skills = skills.replace(s,  "");
			}
		}
		if(skill.indexOf(skills) == 0) {
			return true;
		}
		
		return possible;
	}

 

해결전략은 skill_trees를 하나씩 돌려보면서 

해당 문자가 skill에 없으면 skill_trees[i]에서 없앤다.

중복이 없기 때문에 나머지는 다 사라지고 skill에 해당하는 문자열만 남을 텐데

남는 문자를 마지막에 skill과 대조해보면 skill에 해당하는 문자열 순서대로 남는지 확인이 가능하다.

이렇게 replace()를 활용했을 때 꽤 괜찮게 풀 수 있는 문제이다.

 

2)

public boolean isPossible(String skill, String skillTree) {
		boolean possible = true;
		
		int prevIdx = skillTree.indexOf(skill.charAt(0));
		int curIdx = 0;
		for(int i=1; i<skill.length(); i++) {
			char c = skill.charAt(i);
			curIdx = skillTree.indexOf(c);
			if(
					(prevIdx>curIdx) && (curIdx != -1) // skill이 있긴 하지만 순서가 잘못된 경우
				  || (prevIdx==-1 && curIdx != -1) // 중간이 빈 경우
				) 
			{
				return false;
			}
			prevIdx = curIdx;
		}
		
		return possible;
	}

 

indexOf()를 활용한 방법.

for문을 굳이 돌릴필요 없이 indexOf 메서드를 알고 있다면 활용해서 전 위치와 현 위치를 비교하면 된다.

다만 false를 return하는 경우를 잘 알아야할 것이고

prevIdx = curIdx 현 위치를 전 위치로 넣어주는 작업에 대해서도 잘 파악해야한다.

 

 

 

sas-study.tistory.com/342

[Java 알고리즘] 프로그래머스, 스킬트리