프로그래머스 Lv2. 스킬트리(파이썬)

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

풀이

---

언뜻 봤을때 위상정렬로 풀어야하나 싶었지만, 그냥 skill의 우선순위를 표시해가며 풀어도 될 것 같아서 모든 알파벳의 우선순위를 0으로 초기화 하고, skill의 알파벳 순서대로 1씩 추가해준 값을 idx 배열에 저장해 주었다. 이를 이용해 비교하려는 문자열을 훑으면서 현재의 우선순위보다 높으면 잘못된 순서이므로 flag를 표시하고 끝낸다.

알파벳은 ABC...XYZ를 0번부터 25번의 인덱스로 사용하고 싶어서 ASCII 값을 이용해 바꿔주었다.(AToI함수)

python3

def AToI(A):
    return ord(A) % 65
def solution(skill, skill_trees):
    answer=0
    idx = [0] * 26                      #우선순위 담은 배열, 작을수록 우선순위 높음
    j=1
    for i in range(len(skill)):    #skill 순서대로 우선순위 갱신
        idx[AToI(skill[i])] = j
        j+=1
    for string in skill_trees:
        j=1; flag = True                  #j가 현재의 우선순위
        for i in range(len(string)):
            if idx[AToI(string[i])] > j:        #현재의 우선순위보다 크면 x
                flag = False
                break
            elif idx[AToI(string[i])] == j:  #비교값이 현재의 우선순위면 다음 우선순위로
                j+=1
        if flag: answer+=1                        #끝까지 올바른 우선순위로 지나왔으면 답+=1
    return answer