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

https://school.programmers.co.kr/tryouts/32181/challenges

문제의 핵심은 주어진 skill이 skill_trees 내 skill_tree에 올바른 순서로 들어가있는가이다. skill의 subsequence만 들어가도 무방하다.

문제에서 주어진 배열의 길이를 보았을 때 시간 복잡도를 고려할 만한 문제는 아님을 판단할 수 있어야 한다. 그리고 문제 요구 사항을 보고 어떤 자료구조를 사용할 것인지에 대한 감이 빨리 와야 할 것 같다.

---

나의 첫 풀이

def solution(skill, skill_trees):
    """
    skill_trees 탐색하되...skill의 순서가 어떻게 되는지 체크
    """
    answer = 0
    for sk in skill_trees:
        sk = "".join([chr for chr in sk if chr in skill])
        if sk in skill: # Bug
            answer += 1

    print(skill)

    return answer

정확성 테스트에서 아주 일부 케이스만 맞힌 답이었다. 시간이 없어서 일단은 저렇게 제출을 했는데 어떤 케이스를 고려하지 못한 건지가 쉽게 떠오르지 않았다. 애초에 문제접근부터 좀 잘못되었던 것 같다.

근데 지금 다시 실행해보니 애초에 주어져있던 샘플 케이스부터 틀린 건데 대체 제출할 생각을 어떻게 한 거지..? ㅎㅎ 일단 위의 코드에서 문제가 되는 부분은 if sk in skill 부분이다. 이 경우에는 subsequence 냐에만 초점을 맞춰서 skill의 중간점부터 등장하는 subsequence인 경우에는 answer에 포함을 시키면 안된다는 걸 간과했다.

즉, 이 풀이는 "CBD"가 주어진 skill이고, skill tree "BADF" 가 주어졌을 때에 필요한 "BD"만 보고 얘기했을 때 "C"가 선행되지 않았기 때문에 문제가 되는 케이스를 고려하지 못한다.

따라서, 저런 케이스를 따질 수 있을 만한 풀이를 고려해야 한다. 위의 풀이를 최대한 건드리지 않고 문제가 되는 부분만을 수정해 보았다.

---

두 번째 풀이

def solution(skill, skill_trees):
    """
    skill_trees 탐색하되...skill의 순서가 어떻게 되는지 체크
    """
    answer = 0
    for sk in skill_trees:
        sk = "".join([chr for chr in sk if chr in skill])
        for c_sk, c_skill in zip(sk, skill):
            if c_sk != c_skill:
                break
        else:
            answer += 1

    return answer

zip 같은 경우에는 length가 같은 시퀀스뿐 아니라 length가 다른 두 시퀀스 또한 묶어줄 수 있다. 이 경우에는 그냥 짧은 시퀀스에 맞추고 긴 시퀀스의 남는 부분은 버리는 형식으로 zip이 된다.

 

따라서, 이 경우에도 알아서 긴 시퀀스의 남는 부분은 버릴 것이므로 위와 같이 zip으로 묶어준 후, 두 원소가 다르다면 해당 skil tree는 skip하는 형태로 풀 수 있다. 다만, 이는 skill과 skill_tree에 중복되는 스킬이 등장하지 않는다는 점을 기반으로 한다.

---

세 번째 풀이

마지막 세 번째 풀이는 큐(Queue)를 이용한 풀이다. 실제로 skill의 경우 앞에서부터 하나하나 탐색해나가야 한다는 점에서 FIFO 구조의 큐가 적합한 자료형이라고 할 수 있다. 우선 skill을 deque(덱)를 이용해서 큐 자료구조형으로 바꿔준다. (deque는 FIFO와 LIFO가 모두 가능한 구조라, dequeue와 pop 연산을 모두 상수시간에 수행할 수 있다) 따라서 skill_trees 내부의 각 skill_tree마다 다시 loop을 돌면서, 각 sk가 skill_dq에 존재하는지(즉, 순서에 영향을 받는 스킬인지를 판단) & 해당 sk가 skill_dq에 정의되어 있는 순서대로 나와있는지를 판단해야 한다. sk가 skill_dq에 존재하면서 정의되어 있는 순서대로 나와있지 않다면, 즉 skill_dq에서 popleft를 했을 때 (가장 첫번째 원소를 dequeue, a.k.a. popleft를 했을 때) sk와 동일하지 않다면 해당 skill_tree는 잘못된 skill_tree이므로 해당 tree에 대한 탐색을 종료하고 break문으로 탈출한다. 그게 아니고 탐색이 정상적으로 종료되었다면 answer를 하나 증가시켜준다.위의 과정을 코드로 표현하면 아래와 같다.

from collections import deque

def solution(skill, skill_trees):
	answer = 0
    
    for skill_tree in skill_trees:
    	skill_dq = deque(skill) # skill을 deque 형태로 변경
        
    	for sk in skill_tree:
        	if sk in skill_dq and sk != skill_dq.popleft():
            		break
        else:
          	answer += 1
    
    return answer