[자바] 프로그래머스 - 스킬트리 (Lv2, Java)

문제 : Programmers-스킬트리

문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

 

필요 알고리즘 개념

• 구현, 문자열 
  • 문자열을 활용해 문제에서 제시된대로 구현하는 문제이다.

 

풀이 1 - 쉽게 생각해볼만한 방법!

  우선 가장 쉽게 생각해볼 수 있는 방법은, skill_trees[]의 각 문자열에서 skill에 들어있는 문자열을 제외한 나머지를 모두 제거하는 방식이다.

 

  예를들어 '입출력 예'의 경우 다음과 같이 변환한다. (skill = CBD)

"BACDE" -> "BCD"
"CBADF" -> "CBD"
"AECB" -> "CB"
"BDA" -> "BD"

 

  그렇게되면 skill이라는 문자열에서 앞에서부터 변환한 문자열이 나온다면 가능한 스킬트리이다. 즉, skill.indexOf(변환한 문자)가 0인지 확인하면 된다.

예를들어

"BACDE" -> "BCD" -> "CBD"에 존재하지 않으므로 불가능
"CBADF" -> "CBD" -> "CBD와 동일하므로 가능
"AECB" -> "CB" -> "CBD"의 앞부분 "CB"에 해당하므로 가능
"BDA" -> "BD" -> "CBD"에 포함되긴 하지만, 앞에서부터 나오는게 아니므로 불가능

 

 

풀이1 코드 : github

/**
 * 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
 */
class Solution {
    public int solution(String skill, String[] skill_trees) {
        int answer = 0;
        for (String cur : skill_trees) {	// skill_trees의 문자열 하나씩 보면서
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < cur.length(); i++) {	
                if (skill.contains(cur.charAt(i) + ""))// 문자 순서대로 skill에 포함되는것만
                    sb.append(cur.charAt(i));	// 따로 빼둠.
            }
            answer += skill.indexOf(sb.toString())==0 ? 1 : 0;
        }
        return answer;
    }
}

 

---

 

풀이 2 - 정규식

  풀이1에서 직접 skill에 없는 문자열을 제거해줬는데, 사실 정규식으로 한방에 제거가 가능하다!

 

 

풀이2 코드 : github

/**
 * 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
 */
class Solution {
    public int solution(String skill, String[] skill_trees) {
        int answer = 0;
        for (String cur : skill_trees) {
            cur = cur.replaceAll("[^"+skill+"]", "");	//정규식으로 제거
            answer += skill.indexOf(cur)==0 ? 1 : 0;
        }
        return answer;
    }
}

 

---

 

풀이 3 - 더 효율적으로 못함?!

  원래 문자열 관련 연산이나 정규식 관련 연산은 느리다. 더 효율적으로 할 방법이 없을까? 당연히 있다. 빠르게 해보자.

 

풀이1 동작시간

 

풀이2 동작시간

 

풀이3 동작시간 (위보다 몇백배 빠르다 ㅋㅋ)

 

  잘 생각해보면 문자열 자체를 변환하지 않더라도, 규칙성을 찾아 풀어볼 수 있다.

 

1. skill_trees[] 에서 현재 보고 있는 문자열을 cur이라고 하겠다.

 

2. skill의 각 문자의 위치를 cur에서 찾아본다고 해보자. cur에서 skill에서 현재 보고 있는 문자의 위치를 idx라고 하겠다.

 

3. 그리고 bf는 이전 문자의 idx이다.

 

4. 그렇다면 기본적으로 생각해볼 수 있는건 idx < bf 라면 스킬 순서가 어긋난 것이니 불가능한 스킬트리임을 알 수 있다. 무슨말이냐면 skill이 CBD, cur이 BACDE 라고 해보자. skill의 첫번째 문자인 'C'에 대해 idx는 2가 된다. 그리고 'B'를 찾아보면 idx = 0이 된다. idx<bf(bf='C'의 idx인 2) 이므로, 'C'보다 'B'가 먼저나왔으므로 순서가 어긋난 것임을 알 수 있다.

 

5. 그리고, 한번이라도 idx가 -1 (못찾는다면) 이었다면 그 뒤로는 항상 -1만 가능하다. 이것도 무슨말이냐면 skill이 CBD, cur이 CD 라고 해보자. skill의 'C'는 idx=0, 'B'는 idx=-1, 'D'는 idx=1 이다. 중간에 -1이 있었는데, 다시한번 -1이 아닌게 나왔으므로 불가능한 경우이다. 만약에 skill이 CBDE, cur이 CB라면 'C'는 idx=0, 'B'는 idx=1, 'D'는 idx=-1, 'E'는 idx=-1 이므로 이처럼 -1이 한번이라도 나온 이후 그 뒤로 전부 -1이라면 가능한 경우이다.

 

 

  그럼 이걸 어떻게 구현해야 편한지 생각해보자. 처음으로 idx가 -1이 된 시점을 찾아두는것도 좋지만, 그냥 idx가 -1일 경우 27이상의 값(나올 수 없는 큰 인덱스값. 즉 그냥 무한대라고 칠 수 있는 값)으로 변경하면 된다. 그럼 idx<bf 로직 하나만으로 체크가 가능하다.

 

 

풀이3 코드 : github

/**
 * 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
 */
class Solution {
    private boolean isValid(String skill, String cur) {
        int bf = 0;
        for (int i = 0; i < skill.length(); i++) {
            int idx = cur.indexOf(skill.charAt(i));
            if (idx == -1) idx = Integer.MAX_VALUE;
            if (idx < bf) return false;
            bf = idx;
        }
        return true;
    }

    public int solution(String skill, String[] skill_trees) {
        int answer = 0;
        for (String cur : skill_trees) {
            answer += isValid(skill, cur) ? 1 : 0;
        }
        return answer;
    }
}