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

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

프로그래머스

 

접근

---

• skill의 순서와 skill tree의 원소들의 순서가 동일한지를 점검해야 한다 → 투 포인터 활용

 

로직

---

1. skill에 어떤 스킬들이 포함되어 있는지 확인하기 위해 Set 자료구조를 활용한다
2. skill_trees에 대해 반복문을 수행한다
3. skill에 대한 포인터와 target에 대한 포인터를 선언한다. skill의 포인터와 target의 포인터가 각각의 데이터 크기보다 작을 때까지만 반복문을 수행한다. 
   
   1. skill의 포인터가 가리키고 있는 원소와 target의 포인터가 가리키고 있는 원소가 같다면, 두 개의 포인터 모두 1 증가시킨다
   2. 동일하지 않고, target 포인터가 가리키고 있는 원소가 skill에 포함되어 있는 원소라면 선행 순서를 지키지 않음을 의미하므로 반복문을 종료한다
   3. 1번과 2번이 아닌 경우, 조건에 포함되지 않은 스킬이므로 다음 skill 원소를 확인하기 위해 target의 포인터를 1 증가시킨다
4. 포인터에 대한 반복문의 수행이 끝난 후, 선행 스킬 조건이 만족된 경우 answer 값을 1 증가시킨다

 

 

 

코드

---

1. Swift 풀이

---

func solution(_ skill:String, _ skill_trees:[String]) -> Int {

    let skill = Array(skill)
    let skillElement = Set<Character>(skill)
    
    var answer = 0
    
    for target in skill_trees {
    
        let target = Array(target)
        
        var sPoint = 0, tPoint = 0
        var isValid = true
        
        while sPoint < skill.count && tPoint < target.count {
            if skill[sPoint] == target[tPoint] {
                sPoint += 1
                tPoint += 1
            }
            else if skillElement.contains(target[tPoint]) {
                isValid = false
                break
            }
            else {
                tPoint += 1
            }
        }
        if isValid {
            answer += 1
        }
    }
    
    return answer
}

 

2. Python 풀이

---

def solution(skill, skill_trees):
    
    skill = list(skill)
    skillElement = set(skill)
    
    answer = 0
    for target in skill_trees:
        
        target = list(target)
        
        sPoint = 0
        tPoint = 0
        
        isValid = True
        
        while sPoint < len(skill) and tPoint < len(target):
            
            if skill[sPoint] == target[tPoint]:
                sPoint += 1
                tPoint += 1
            elif target[tPoint] in skillElement:
                isValid = False
                break
            else:
                tPoint += 1
        
        if isValid :
            answer += 1
            
    return answer