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

park geonwoo·2024년 10월 30일

목록 보기

30/32

https://school.programmers.co.kr/learn/courses/30/lessons/49993?language=python3

이번 문제는 선행 스킬 순서를 기반으로 유효한 스킬 트리를 판별하고, 가능한 스킬 트리의 개수를 구하는 문제입니다. 주어진 선행 스킬 순서를 따르면서 스킬을 배우는 사용자들의 스킬 트리가 유효한지 판단해야 합니다. 만약 유효하다면 그 스킬 트리를 카운트하고, 최종적으로 가능한 스킬 트리의 총 개수를 반환합니다. 유효하지 않은 스킬 트리는 제외됩니다.

문제 이해

문제 요약

목표:
- 선행 스킬 순서 skill과 여러 개의 사용자 스킬 트리 skill_trees가 주어질 때, skill의 순서를 따르는 skill_trees의 개수를 구합니다.
선행 스킬 순서 (skill):
- 스킬은 알파벳 대문자로 표기되며, 순서가 중요합니다.
- 예: "CBD"는 C를 먼저 배우고, 그 다음 B, 그 다음 D를 배워야 합니다.
스킬 트리 (skill_trees):
- 사용자가 스킬을 배우는 순서를 나타냅니다.
- skill에 포함되지 않은 스킬은 순서에 관계없이 배울 수 있습니다.
유효한 스킬 트리의 조건:
- skill에 포함된 스킬들은 주어진 순서를 반드시 따라야 합니다.
- skill에 포함되지 않은 스킬들은 아무 위치에나 배치될 수 있습니다.
- 예:
  - skill = "CBD"
  - skill_trees = ["BACDE", "CBADF", "AECB", "BDA"]
    - "BACDE": B가 C보다 먼저 등장 → 유효하지 않음
    - "CBADF": C → B → D 순 → 유효함
    - "AECB": C → B → D 순 → 유효함
    - "BDA": B가 C보다 먼저 등장 → 유효하지 않음
  - 따라서 가능한 스킬 트리의 개수는 2입니다.

예제 분석

예제 입력 1:

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

예제 출력 1:

해석:

"BACDE": B가 C보다 먼저 → 유효하지 않음
"CBADF": C → B → D 순 → 유효함
"AECB": C → B → D 순 → 유효함
"BDA": B가 C보다 먼저 → 유효하지 않음
총 유효한 스킬 트리의 개수: 2

해결 방법

접근 방식

스킬 트리가 유효한지 판단하기 위해, 각 스킬 트리를 순회하며 skill의 순서를 따르는지 확인합니다. 구체적인 방법은 다음과 같습니다:

포인터 기반 검사:
- skill의 각 스킬에 대해 포인터를 사용하여 현재 기대하는 스킬을 추적합니다.
- 스킬 트리를 순회하면서 skill에 포함된 스킬이 등장할 때마다 포인터를 이동합니다.
- 스킬 트리 내에서 skill의 순서를 벗어나는 스킬이 등장하면 유효하지 않은 스킬 트리로 간주합니다.
유효성 판별 기준:
- 스킬 트리에서 skill에 포함된 스킬들이 skill의 순서대로 등장하면 유효한 스킬 트리입니다.
- skill에 포함되지 않은 스킬들은 무시합니다.
- 모든 skill 스킬들이 순서를 지키며 등장했다면, 유효한 스킬 트리로 카운트합니다.

알고리즘 단계

초기화:
- 유효한 스킬 트리의 개수를 세기 위한 count 변수를 0으로 초기화합니다.
각 스킬 트리 검사:
- 각 skill_tree에 대해 다음을 수행합니다:
  a. skill의 순서를 추적하기 위한 포인터 pointer를 0으로 초기화합니다.
  b. 스킬 트리를 순회하면서:
  - 현재 스킬이 skill에 포함되지 않으면 무시합니다.
  - 현재 스킬이 skill[pointer]와 일치하면 포인터를 이동시킵니다.
  - 현재 스킬이 skill[pointer]와 일치하지 않으면 유효하지 않은 스킬 트리로 간주하고 검사 중단합니다.
  c. 스킬 트리를 모두 검사한 후, 유효한 스킬 트리라면 count를 증가시킵니다.
결과 반환:
- 최종적으로 유효한 스킬 트리의 개수를 반환합니다.

예제 검증

예제 입력 1:

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

"BACDE":
- B ≠ C (skill[0]) → 유효하지 않음
"CBADF":
- C == C (skill[0]) → 포인터 이동 → B == B (skill[1]) → 포인터 이동 → D == D (skill[2]) → 포인터 이동 → 유효함
"AECB":
- C == C (skill[0]) → 포인터 이동 → B == B (skill[1]) → 포인터 이동 → 유효함
"BDA":
- B ≠ C (skill[0]) → 유효하지 않음
총 유효한 스킬 트리의 개수: 2

코드 구현

아래는 위의 접근 방식을 구현한 파이썬 코드입니다. 코드는 간결하면서도 효율적으로 문제를 해결할 수 있도록 작성되었습니다.

def solution(skill, skill_trees):
    count = 0  # 유효한 스킬 트리의 개수를 세기 위한 변수
    skill_set = set(skill)  # skill에 포함된 스킬을 빠르게 확인하기 위한 집합

    for tree in skill_trees:
        pointer = 0  # skill의 현재 기대 스킬을 가리키는 포인터
        valid = True  # 스킬 트리가 유효한지 여부를 나타내는 변수

        for char in tree:
            if char not in skill_set:
                continue  # skill에 포함되지 않은 스킬은 무시

            if pointer < len(skill) and char == skill[pointer]:
                pointer += 1  # 기대하는 스킬과 일치하면 포인터를 이동
            elif pointer >= len(skill) or (pointer < len(skill) and char != skill[pointer]):
                # 기대하는 스킬과 일치하지 않거나, skill 순서를 초과한 스킬이 등장하면 유효하지 않음
                valid = False
                break  # 더 이상 검사할 필요 없음

        if valid:
            count += 1  # 유효한 스킬 트리이면 카운트

    return count

코드 설명

1. 함수 정의

def solution(skill, skill_trees):
    ...

skill: 선행 스킬 순서를 나타내는 문자열 (예: "CBD")
skill_trees: 사용자들이 만든 스킬 트리의 리스트 (예: ["BACDE", "CBADF", "AECB", "BDA"])
반환값: 유효한 스킬 트리의 개수 (정수)

2. 초기화

    count = 0  # 유효한 스킬 트리의 개수를 세기 위한 변수
    skill_set = set(skill)  # skill에 포함된 스킬을 빠르게 확인하기 위한 집합

count: 유효한 스킬 트리의 수를 저장합니다.
skill_set: skill에 포함된 스킬을 빠르게 확인하기 위해 집합으로 변환합니다.

3. 각 스킬 트리 검사

    for tree in skill_trees:
        pointer = 0  # skill의 현재 기대 스킬을 가리키는 포인터
        valid = True  # 스킬 트리가 유효한지 여부를 나타내는 변수

        for char in tree:
            if char not in skill_set:
                continue  # skill에 포함되지 않은 스킬은 무시

            if pointer < len(skill) and char == skill[pointer]:
                pointer += 1  # 기대하는 스킬과 일치하면 포인터를 이동
            elif pointer >= len(skill) or (pointer < len(skill) and char != skill[pointer]):
                # 기대하는 스킬과 일치하지 않거나, skill 순서를 초과한 스킬이 등장하면 유효하지 않음
                valid = False
                break  # 더 이상 검사할 필요 없음

        if valid:
            count += 1  # 유효한 스킬 트리이면 카운트

스킬 트리 순회:
- 각 skill_tree에 대해:
  - pointer를 0으로 초기화하여 skill의 첫 번째 스킬을 기대합니다.
  - valid를 True로 초기화하여 현재 스킬 트리가 유효한지 여부를 추적합니다.
스킬 트리 내 스킬 순회:
- 스킬 트리의 각 스킬 char에 대해:
  - char가 skill_set에 포함되지 않으면 무시합니다.
  - char가 skill_set에 포함되면:
    - pointer가 skill의 길이보다 작고, char가 skill[pointer]와 일치하면:
      - pointer를 1 증가시켜 다음 스킬을 기대합니다.
    - 그렇지 않으면 (즉, char가 기대하는 스킬과 다르거나, skill 순서를 초과한 경우):
      - valid를 False로 설정하고, 현재 스킬 트리는 유효하지 않으므로 루프를 중단합니다.
유효한 스킬 트리 카운트:
- 루프가 끝난 후, valid가 True이면 현재 스킬 트리는 유효한 스킬 트리이므로 count를 1 증가시킵니다.

4. 결과 반환

    return count

모든 스킬 트리를 검사한 후, 유효한 스킬 트리의 총 개수를 반환합니다.

예제 실행

예제 입력 1:

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

함수 호출:

print(solution("CBD", ["BACDE", "CBADF", "AECB", "BDA"]))

실행 과정:

"BACDE":
- 'B': skill[0]은 'C' → 유효하지 않음 → valid = False
"CBADF":
- 'C': skill[0] = 'C' → pointer = 1
- 'B': skill[1] = 'B' → pointer = 2
- 'A': skill[2] = 'D'와 다름 → 무시
- 'D': skill[2] = 'D' → pointer = 3
- 'F': skill_set에 없음 → 무시
- 유효함 → count = 1
"AECB":
- 'A': skill_set에 없음 → 무시
- 'E': skill_set에 없음 → 무시
- 'C': skill[0] = 'C' → pointer = 1
- 'B': skill[1] = 'B' → pointer = 2
- 유효함 → count = 2
"BDA":
- 'B': skill[0]은 'C' → 유효하지 않음 → valid = False

최종 결과: 2

예제 출력:

시간 복잡도 및 효율성

시간 복잡도

스킬 트리 검사:
- 각 skill_tree의 길이를 L이라 할 때, 각 스킬 트리를 순회하는 데 O(L) 시간이 걸립니다.
- skill_trees의 개수를 T라고 할 때, 전체 시간 복잡도는 O(T * L)입니다.
제한 조건:
- T는 최대 20, L은 최대 26이므로, 전체 시간 복잡도는 O(20 * 26) = O(520)으로 매우 효율적입니다.

공간 복잡도

추가 공간:
- skill_set: O(S) 공간 (S는 skill의 길이, 최대 26).
- 기타 변수 (count, pointer, valid 등): O(1) 공간.
전체 공간 복잡도: O(S)으로, 매우 작습니다.

알고리즘 및 자료구조 설명

알고리즘: 포인터 기반 순차 검사

설명:
- skill의 순서를 따르는지 확인하기 위해, 포인터를 사용하여 현재 기대하는 스킬을 추적합니다.
- 스킬 트리를 순회하면서, skill에 포함된 스킬이 등장할 때마다 포인터를 이동시킵니다.
- 만약 등장하는 스킬이 기대하는 스킬과 다르거나, skill의 순서를 초과하는 경우 유효하지 않은 스킬 트리로 간주합니다.
장점:
- 간단하면서도 효율적으로 스킬 트리의 유효성을 검사할 수 있습니다.
- 불필요한 추가 자료구조를 사용하지 않아 메모리 사용이 최소화됩니다.

자료구조: 집합 (Set)

설명:
- skill_set을 사용하여, 각 스킬이 skill에 포함되는지 빠르게 확인할 수 있습니다.
- 집합의 O(1) 평균 시간 복잡도로 포함 여부를 검사할 수 있어, 효율적인 구현이 가능합니다.
장점:
- 스킬의 포함 여부를 빠르게 판단할 수 있습니다.
- skill의 길이가 짧으므로, 집합 생성과 조회가 매우 빠릅니다.

park geonwoo

이전 포스트

[백준] 20165번 인내의 도미노 장인 호석

다음 포스트

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

코딩테스트

문제 이해

문제 요약

예제 분석

해결 방법

접근 방식

알고리즘 단계

예제 검증

코드 구현

코드 설명

1. 함수 정의

2. 초기화

3. 각 스킬 트리 검사

4. 결과 반환

예제 실행

시간 복잡도 및 효율성

시간 복잡도

공간 복잡도

알고리즘 및 자료구조 설명

알고리즘: 포인터 기반 순차 검사

자료구조: 집합 (Set)

[백준] 20165번 인내의 도미노 장인 호석

[백준] 28324번 스케이트 연습

0개의 댓글