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

문제설명

skill_trees 리스트에 있는 문자열의 알파벳 순서가 skill 문자열의 순서대로 이루어져있는지 판단하고 그 갯수를 리턴하는 문제입니다.

입출력 예를 봐도 알 수 있지만, 여기서 주의할 점은 skill_trees의 "BDA"는 불가능한 스킬 트리입니다. B와 D의 순서는 맞았지만 B를 위해 선행되어야 하는 C가 없기 때문입니다.

그렇지만 "CBA"는 가능합니다. skill의 문자열 "CBD"와 같이  "CBA"는 C -> B로 스킬 순서가 되므로 아무 문제가 없고 D는 없지만 순서가 중요하지 모든 skill의 문자열이 포함되어야 하는 것은 아닙니다.

 

접근방법

skill 문자열의 가장 마지막 문자부터 처음 문자까지 포문을 돌면서

유저의 문자열에 해당 문자열이 있는지 체크하고 now_idx를 갱신해가는 것을 포인트로 했습니다.

now_idx는 처음에 가장큰 27(스킬트리 문자길이 최대가26입니다)로 설정해 두었고 skill 문자열의 가장 마지막 문자부터 체크하기 때문에 now_idx는 점점 값이 작아지는 방향으로 갱신이 되어야 합니다.

now_idx가 값이 커졌다면 불가능한 스킬트리라는 뜻이 됩니다.

first 플래그는 "BDA"와 같은 스킬 트리를 필터링할 목적으로 두었습니다.

skill 문자열의 문자가 뒤 순서부터 한번이라도 유저의 문자열에 있었다면 그 알파벳 기준으로 skill의 앞 문자는 모두 유저의 문자열에 존재해야 합니다.(선행되는 문자이기 때문)

따라서 "BDA"와 같은 문자열은 for문 안의 else 에서 걸러지게 됩니다.

 

 

내풀이

def solution(skill, skill_trees):
    answer = 0
    for user_skill in skill_trees :
        now_idx = 27
        is_right = True
        first = False

        for idx in range(len(skill)-1,-1,-1):
            if user_skill.count(skill[idx]) > 0:
                first = True
                tmp_idx = user_skill.index(skill[idx])
                if now_idx > tmp_idx:
                    now_idx = tmp_idx
                else :
                    is_right = False
                    break
            else :
                if first == True :
                    is_right = False

        if is_right:
            answer += 1
    return answer

 

다른사람 풀이1

def solution(skill,skill_tree):
    answer=0
    for i in skill_tree:
        skillist=''
        for z in i:
            if z in skill:
                skillist+=z
        if skillist==skill[0:len(skillist)]:
            answer+=1
    return answer

개인적으로 이 풀이가 제일 직관적인것 같습니다.

유저의 스킬트리의 알파벳(z)이 skill문자열에도 있으면 skillist라는 새로운 문자열에 추가하는 방식입니다.

최종적으로 skillist와 skill이 같다면 올바른 스킬트리임을 알 수 있습니다.

 

다른사람 풀이2 (조금 변형함)

def solution(skill, skill_trees):

    answer = 0

    for elem in skill_trees:
        skill_list = list(skill)
        flag = True

        for s in elem:
            if s in skill:
                if s == skill_list.pop(0):
                    if len(skill_list) == 0 : // 이 부분 추가함
                        break
                else :
                    flag = False
                    break

        if flag == True:
            answer += 1

    return answer

다른사람풀이 1과 전체적은 흐름은 비슷합니다.

차이점은 유저의 스킬트리의 알파벳이 skill 문자열에도 있다면 skill을 리스트로 만들어둔 skill_list에서 pop하고 서로 같은지 비교하여 알파벳 순서를 보장할 수 있습니다.