프로그래머스

프로그래머스 스킬트리 풀이: 선행 스킬 접두사 판정

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

  • 문제: 스킬트리
  • 출처: 프로그래머스, Summer/Winter Coding(~2018)
  • 자체 판단 난이도: Level 2

선행 스킬에 포함된 스킬만 골라 원래 순서와 비교하면 되는 문제다. 불필요한 스킬을 무시하고 필요한 스킬의 순서를 접두사로 판정하는 문자열 처리가 핵심이므로 Level 2로 판단했다.

1. 문제 요약

skill은 반드시 배워야 하는 선행 스킬의 순서다. 예를 들어 skill = "CBD"라면 C를 배운 뒤 B, 그다음 D를 배워야 한다.

skill_trees의 각 문자열은 사용자가 스킬을 배우는 순서다. 선행 스킬에 포함되지 않는 다른 스킬은 어느 위치에서 배워도 되지만, 선행 스킬에 포함된 스킬은 skill에 정해진 순서를 지켜야 한다.

가능한 스킬트리의 개수를 반환한다.

  • skill의 길이는 1 이상 26 이하다.
  • 스킬과 스킬트리의 문자는 대문자다.
  • skill_trees의 길이는 1 이상 20 이하다.
  • 각 스킬트리에는 같은 스킬이 중복되지 않는다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

구간 판정

각 스킬트리에서 skill에 포함된 문자만 순서대로 추출한다. 추출한 문자열이 skill의 앞부분과 같으면 가능한 스킬트리다.

skill = "CBD"
skill_tree = "CBADF"

선행 스킬만 추출한 결과 = "CBD"
skill의 접두사와 일치 = 가능

반대로 skill_tree = "BACDE"라면 선행 스킬만 추출한 결과가 "BCD"가 되지만, B가 C보다 먼저 나왔으므로 skill의 접두사 "CBD"와 일치하지 않는다.

필터링한 스킬 순서가 접두사인지 확인하기

사용자가 선행 스킬 중 일부만 배워도 된다. 따라서 추출된 문자열이 반드시 skill 전체와 같아야 하는 것이 아니라, skill의 길이만큼 잘라낸 앞부분과 같아야 한다.

skill = "CBD"
추출 결과 = "CB"
skill의 접두사 = "CB"

이 경우 아직 D를 배우지 않은 상태이지만 순서는 올바르므로 가능한 스킬트리다. 선행 스킬이 하나도 등장하지 않아 추출 결과가 빈 문자열인 경우도 빈 접두사와 일치하므로 가능하다.

상태 전이와 경계 처리

스킬트리를 왼쪽부터 확인한다.

  1. 현재 문자가 skill에 없으면 선행 조건과 무관하므로 건너뛴다.
  2. skill에 있는 문자만 learned에 추가한다.
  3. learned가 skill의 접두사인지 확인한다.
  4. 접두사이면 정답 개수를 1 증가시킨다.

Python의 skill.startswith(learned)는 learned가 skill보다 짧은 경우에도 접두사 여부를 정확히 판정한다. learned가 빈 문자열이면 True이므로 선행 스킬을 하나도 배우지 않은 스킬트리도 자연스럽게 처리한다.

오답 접근과 반례

스킬트리에 선행 스킬이 몇 개 포함되었는지만 세고 순서를 확인하지 않으면 오답이다.

skill = "CBD"
skill_tree = "BCD"

세 선행 스킬이 모두 들어 있지만 올바른 순서는 CBD다. B가 먼저 나왔으므로 가능하지 않다.

또한 learned == skill만 허용하면 일부 선행 스킬만 배운 정상적인 경우를 놓친다.

skill = "CBD"
skill_tree = "CBADF"
추출 결과 = "CBD"  # 전체를 배운 경우

반대로 skill_tree = "CA"라면 추출 결과 "C"만 남고, 이는 skill의 접두사이므로 가능한 스킬트리다. 전체 일치가 아니라 접두사 일치가 필요하다.

시간·공간 복잡도

스킬트리의 모든 문자를 한 번씩 확인하므로 전체 시간 복잡도는 O(T)다. 여기서 T는 모든 스킬트리 문자열의 문자 수 합이다. 현재 스킬트리에서 선행 스킬만 저장하는 문자열의 길이는 최대 26이므로 추가 공간 복잡도는 스킬트리 하나 기준 O(S)이며, S는 skill의 길이다.

3. 문제 해결 코드 (Python)

def solution(skill, skill_trees):
    answer = 0

    for skill_tree in skill_trees:
        learned = "".join(
            skill_name for skill_name in skill_tree if skill_name in skill
        )

        if skill.startswith(learned):
            answer += 1

    return answer

learned에는 선행 스킬에 속한 문자만 원래 순서대로 남는다. 이 문자열이 skill의 접두사라면, 사용자가 배운 선행 스킬들이 허용된 순서에서 벗어나지 않았다는 뜻이다.

복사해 실행할 테스트

아래 검사를 풀이 코드 아래에 붙여 python 파일명.py로 실행하면 필수 스킬의 접두사 순서를 확인할 수 있다.

assert solution("CBD", ["BACDE", "CBADF", "AECB", "BDA"]) == 2
assert solution("CBD", ["C", "CA", "A", "BD"]) == 3

4. 공식 예제와 추가 검증

공식 예제와 선행 스킬 일부만 배우는 경우, 선행 스킬이 전혀 등장하지 않는 경우를 Python 코드로 실행했다.

공식 예제

입력:
skill = "CBD"
skill_trees = ["BACDE", "CBADF", "AECB", "BDA"]

기대 출력: 2
확인 결과: 통과
검증 목적: 선행 스킬의 순서와 무관한 스킬을 함께 처리하는지 확인

추가 검증 1: 일부 선행 스킬만 배우는 경우

입력: skill = "ABC", skill_trees = ["AB", "AC", "XYZ", "CBA"]
기대 출력: 2
확인 결과: 통과
검증 목적: "AB"와 선행 스킬이 없는 "XYZ"를 허용하고 잘못된 "AC", "CBA"를 제외하는지 확인

추가 검증 2: 선행 스킬이 전혀 없는 경우

입력: skill = "XYZ", skill_trees = ["AAAA", "BCDE", "XYZ", "XAYBZ"]
기대 출력: 4
확인 결과: 통과
검증 목적: 빈 추출 결과와 선행 스킬 전체·일부 추출 결과를 모두 처리하는지 확인

추가 검증 3: 선행 스킬 하나

입력: skill = "A", skill_trees = ["BCDE", "AB", "BA"]
기대 출력: 3
확인 결과: 통과
검증 목적: 선행 스킬이 하나일 때 A가 포함된 위치와 관계없이 가능한지 확인

5. 다른 풀이 방식 검색 및 비교

큐에 skill을 넣고 선행 스킬을 하나씩 제거하는 방식도 가능하다. 이 글에서는 선행 스킬만 추출한 결과가 허용된 순서의 접두사인지 확인하는 방식으로 구현했다. 두 방식 모두 선행 스킬이 아닌 문자를 무시하고, 선행 스킬이 등장하는 순서를 검사한다는 점은 같다.

마무리

스킬트리는 선행 스킬에 포함된 문자만 추출하면 순서 조건을 간단한 접두사 판정으로 바꿀 수 있다. 선행 스킬을 모두 배울 필요는 없으므로 전체 문자열과 비교하지 않고 skill.startswith(learned)를 사용해야 하며, 이 방식으로 모든 스킬트리를 선형 시간에 확인할 수 있다.

#문자열#프로그래머스#난이도 2