티스토리 뷰

반응형
프로그래머스 스킬트리 Python 풀이

프로그래머스 스킬트리 python


문제

문제

어떤 게임에서 스킬을 배우려면 일정한 선행 스킬 순서를 지켜야 합니다.
예를 들어 CBD라는 스킬 순서가 있다면,
C를 배우기 전에는 B를 배울 수 없고,
B를 배우기 전에는 D를 배울 수 없습니다.

그 외의 스킬(예: A, E, F 등)은 순서와 상관없이 아무 때나 배워도 됩니다.

주어진 것은

  • 선행 스킬 순서 문자열 skill
  • 여러 명의 유저가 만든 스킬 순서 배열 skill_trees

각 유저의 스킬트리가 선행 스킬 순서를 어기지 않았는지를 판별하여,
가능한 스킬트리의 개수를 구하는 문제입니다.


입력 결과
skill = "CBD"
skill_trees = ["BACDE", "CBADF", "AECB", "BDA"]
2

예시 해설

1. "BACDE" → B가 C보다 먼저 나옴 → ❌

2. "CBADF" → 순서 맞음 → ✅

3. "AECB" → C → B 순서 맞음 → ✅

4. "BDA" → B가 C보다 먼저 나옴 → ❌

결과: 가능한 스킬트리 2개



문제 작동 원리

이 문제에서 구해야 하는 값은 “가능한 스킬트리의 개수”입니다.
즉, 주어진 선행 스킬 순서에 따라 순서를 어기지 않은 스킬트리의 개수를 찾는 것입니다.

여기서 중요한 핵심은 선행 스킬에 포함되지 않은 스킬은 무시해야 한다는 점입니다.

즉, 선행 스킬 "CBD"가 있을 때,

  • "AECB"에서 A와 E는 관계가 없습니다.
  • "AECB"에서 실제 비교 대상은 "CB"입니다.
  • "CB""CBD"의 앞부분과 일치하므로 유효합니다.

결국 문제의 본질은

각 스킬트리에서 선행 스킬에 해당하는 문자만 순서대로 추출했을 때,
그 결과가 선행 스킬 문자열의 앞부분과 같은지를 확인하는 것입니다.


문제 아이디어

이 문제의 아이디어는 “필터링 후 비교”입니다.
즉, 복잡하게 순서를 추적하지 않고,
선행 스킬 문자열에 포함된 문자만 모아서 단순히 비교하는 방식입니다.

  1. skill_trees의 각 문자열을 순회합니다.
  2. 각 스킬 문자열에서 skill에 포함된 글자만 골라서 새 문자열 k를 만듭니다.
  3. k의 길이를 N이라 하면, skill[:N]과 비교합니다.
  4. 같으면 순서를 지킨 것이므로 카운트를 하나 증가시킵니다.

이 방식의 장점은 다음과 같습니다.

  • 인덱스 비교나 조건 분기 없이 단순 문자열 비교만 사용합니다.
  • 선행 스킬이 아닌 문자는 자동으로 무시되므로 불필요한 조건 검사가 없습니다.
  • 길이가 달라도 앞부분만 비교하면 되므로 간단합니다.

이 전체 아이디어가 아래 코드의 작동 원리로 구현되어 있습니다.



전체코드

def solution(skill, skill_trees):
    answer = 0
    for skills in skill_trees:
        k=''
        for i in skills:
            if i in skill:
               k+=i
        N=len(k)
        if k==skill[:N]:
            answer+=1
    return answer


결론

이 문제는 순서를 직접 추적하지 않고,
문자열 필터링과 부분 비교만으로 선행 스킬 순서를 검증하는 문제입니다.

즉, 모든 스킬트리에 대해

  1. 선행 스킬만 추출하고,
  2. 그 결과가 선행 스킬 문자열의 앞부분과 같으면 유효하다고 판단합니다.

이 아이디어를 통해 복잡한 조건문이나 인덱스 비교 없이,
단순 문자열 조작만으로 깔끔하게 문제를 해결할 수 있습니다.

결국 구하는 값은 순서를 지킨 유효 스킬트리의 개수이며,
코드는 효율적이고 명확한 로직으로 이를 계산합니다.


반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/10   »
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
글 보관함
반응형