티스토리 뷰
프로그래머스 스킬트리 python
문제
문제
어떤 게임에서 스킬을 배우려면 일정한 선행 스킬 순서를 지켜야 합니다.
예를 들어 CBD
라는 스킬 순서가 있다면,
C를 배우기 전에는 B를 배울 수 없고,
B를 배우기 전에는 D를 배울 수 없습니다.
그 외의 스킬(예: A, E, F 등)은 순서와 상관없이 아무 때나 배워도 됩니다.
주어진 것은
- 선행 스킬 순서 문자열
skill
- 여러 명의 유저가 만든 스킬 순서 배열
skill_trees
각 유저의 스킬트리가 선행 스킬 순서를 어기지 않았는지를 판별하여,
가능한 스킬트리의 개수를 구하는 문제입니다.
예시 해설
1. "BACDE"
→ B가 C보다 먼저 나옴 → ❌
2. "CBADF"
→ 순서 맞음 → ✅
3. "AECB"
→ C → B 순서 맞음 → ✅
4. "BDA"
→ B가 C보다 먼저 나옴 → ❌
결과: 가능한 스킬트리 2개
문제 작동 원리
이 문제에서 구해야 하는 값은 “가능한 스킬트리의 개수”입니다.
즉, 주어진 선행 스킬 순서에 따라 순서를 어기지 않은 스킬트리의 개수를 찾는 것입니다.
여기서 중요한 핵심은 선행 스킬에 포함되지 않은 스킬은 무시해야 한다는 점입니다.
즉, 선행 스킬 "CBD"
가 있을 때,
"AECB"
에서 A와 E는 관계가 없습니다."AECB"
에서 실제 비교 대상은"CB"
입니다."CB"
가"CBD"
의 앞부분과 일치하므로 유효합니다.
결국 문제의 본질은
각 스킬트리에서 선행 스킬에 해당하는 문자만 순서대로 추출했을 때,
그 결과가 선행 스킬 문자열의 앞부분과 같은지를 확인하는 것입니다.
문제 아이디어
이 문제의 아이디어는 “필터링 후 비교”입니다.
즉, 복잡하게 순서를 추적하지 않고,
선행 스킬 문자열에 포함된 문자만 모아서 단순히 비교하는 방식입니다.
skill_trees
의 각 문자열을 순회합니다.- 각 스킬 문자열에서
skill
에 포함된 글자만 골라서 새 문자열k
를 만듭니다. k
의 길이를N
이라 하면,skill[:N]
과 비교합니다.- 같으면 순서를 지킨 것이므로 카운트를 하나 증가시킵니다.
이 방식의 장점은 다음과 같습니다.
- 인덱스 비교나 조건 분기 없이 단순 문자열 비교만 사용합니다.
- 선행 스킬이 아닌 문자는 자동으로 무시되므로 불필요한 조건 검사가 없습니다.
- 길이가 달라도 앞부분만 비교하면 되므로 간단합니다.
이 전체 아이디어가 아래 코드의 작동 원리로 구현되어 있습니다.
전체코드
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
결론
이 문제는 순서를 직접 추적하지 않고,
문자열 필터링과 부분 비교만으로 선행 스킬 순서를 검증하는 문제입니다.
즉, 모든 스킬트리에 대해
- 선행 스킬만 추출하고,
- 그 결과가 선행 스킬 문자열의 앞부분과 같으면 유효하다고 판단합니다.
이 아이디어를 통해 복잡한 조건문이나 인덱스 비교 없이,
단순 문자열 조작만으로 깔끔하게 문제를 해결할 수 있습니다.
결국 구하는 값은 순서를 지킨 유효 스킬트리의 개수이며,
코드는 효율적이고 명확한 로직으로 이를 계산합니다.
'백준 스터디 > 프로그래머스' 카테고리의 다른 글
프로그래머스 [3차] 방금그곡 Python (0) | 2025.10.16 |
---|---|
프로그래머스 혼자 놀기의 달인 Python (1) | 2025.10.14 |
프로그래머스 괄호 변환 Python (0) | 2025.10.03 |
프로그래머스 이모티콘 할인행사 Python (1) | 2025.10.01 |
프로그래머스 삼각 달팽이 문제 python (1) | 2025.09.24 |
- Total
- Today
- Yesterday
- 알고리즘 문제풀이
- 파이썬코딩
- 코딩
- 파이썬문제풀이
- 알고리즘기초
- 문제 풀이
- 브루트포스
- 그리디
- dfs
- 프로그래밍
- C++
- Python
- C++ 알고리즘
- 그리디알고리즘
- c++알고리즘
- 코딩테스트
- 동적계획법
- c언어
- 문제풀이
- 코딩 테스트
- 백준
- DP
- 동적 계획법
- 파이썬
- 문자열처리
- 그래프 탐색
- 알고리즘
- python 알고리즘
- 알고리즘문제풀이
- 객체지향
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |