[프로그래머스] Summer/Winter Coding(~2018) - 스킬트리 - 파이썬(Python)

문제 설명

선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.
예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다.
위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다.
선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요.
 
제한 조건

• 스킬은 알파벳 대문자로 표기하며, 모든 문자열은 알파벳 대문자로만 이루어져 있습니다.
• 스킬 순서와 스킬트리는 문자열로 표기합니다.
  • 예를 들어, C → B → D 라면 CBD로 표기합니다
• 선행 스킬 순서 skill의 길이는 1 이상 26 이하이며, 스킬은 중복해 주어지지 않습니다.
• skill_trees는 길이 1 이상 20 이하인 배열입니다.
• skill_trees의 원소는 스킬을 나타내는 문자열입니다.
  • skill_trees의 원소는 길이가 2 이상 26 이하인 문자열이며, 스킬이 중복해 주어지지 않습니다.

입출력 예
skill	skill_trees	return
"CBD"	["BACDE", "CBADF", "AECB", "BDA"]	2

입출력 예 설명

• BACDE: B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트립니다.
• CBADF: 가능한 스킬트리입니다.
• AECB: 가능한 스킬트리입니다.
• BDA: B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트리입니다.

나의 풀이

 

def solution(skill, skill_trees):
	skill_list = list(skill)
    
    def checker(skill_tree):
    	required_skill = []
        for i in range(len(skill_tree)):
        	if skill_tree[i] in skill_list:
            	required_skill.append(skill_tree[i])
		
        if len(skill_list) == len(required_skill):
        	if skill_list == required_skill:
            	return True
            
            else:
            	return False
		
        else:
        	if required_skill == skill_list[:len(required_skill)]:
            	return True
            
            else:
            	return False
	
    cnt = 0
    for skill_tree in skill_trees:
    	if checker(skill_tree):
        	cnt += 1
	
    return cnt
        

 

접근 방법 및 코드 설명

skill_trees를 도는 for문 안에 내용을 작성해줄수도 있었지만 그러면 코드가 너무 길어지고 더러워질 것 같아서 아예 함수를 새로 만들어주었다.
 
우선적으로 생각한 것은 skill_trees로 받아온 각 값들에 대하여 입력 skill에 포함되지 않는 스킬들은 고려하지 않아도 무방하다는 것이었다.
 
따라서 checker함수에서 해당 과정을 첫 번째로 진행해주었다. 입력으로 받아온 문자열의 각 요소들이 skill_list에 존재할 때만 required_skill 리스트에 append해주었다.
 
그렇게 나온 required_skill과 입력값으로 받아온 skill을 비교해주기만 하면 된다.
 
만약에 required_skill과 skill_list의 길이가 같다면 두 값은 정확히 동일해야만 조건을 만족시킨다.
 
만약 두 리스트의 길이가 다르다면, required_skill은 skill_list의 첫 번째 인덱스부터 required_skill의 길이까지의 값들과 일치해야 한다.
 
 위 두 가지 조건문을 만족시키면 True를, 그렇지 않으면 False를 리턴시키는 방향으로 함수를 작성했으며, skill_trees의 각 skill_tree를 checker 함수의 인자로 넣어주며 값이 True일 땐 cnt를 1씩 증가시켜주었다.
 
 

다른 사람의 풀이

def solution(skill, skill_trees):
	answer = 0
    for skills in skill_trees:
    	skill_list = list(skill)
        
        for s in skills:
        	if s in skill:
            	if s != skill_list.pop(0):
                	break
		
        else:
        	answer += 1
            
	return answer

 
사실 이 문제의 알고리즘 분류는 스택/큐 이다.
 
스택 혹은 큐를 활용할수도 있겠다는 생각은 했지만, 내가 생각해낸 방식을 먼저 검증하고 싶은게 사람 마음이다.
 
문제를 풀고 나서야 다른 사람의 풀이를 볼 수 있었는데, 입력으로 받은 skill을 리스트로 바꿔줘 pop(0)한 값과 skill_trees의 각 값들의 첫 번째 값들을 비교해주면서 문제를 풀었다.
 
로직 자체는 내가 생각한 것과 같다고 볼 수 있지만, 이렇게 하니 훨씬 코드가 깔끔하였고 굳이 매번 skill_tree와 skill의 길이를 구해줄 필요가 없다는 점에서 효율성 측면에서도 탁월했다.
 
재미있는 점은 여지껏 잘 보지 못했던 for - else였는데,
 
for - else는 for문이 break 등에 의해서 도중에 끊기지 않는다면 else문으로 넘어가는 연산을 진행한다.
 
사실 answer += 1 연산을 if s != skill_list.pop(0) 이후의 else문에 붙여줘도 크게 문제가 없지만, 답을 계산하는 코드를 아예 for문 밖으로 빼줌으로써 가독성이 높아진 것을 확인할 수 있었다.
 
또한, 이 코드에서는 collections.deque를 활용해주는 것이 훨씬 좋아보인다.
 
이전 글에서도 정리한 적 있지만, 일반적인 파이썬의 리스트는 정적 배열을 기반으로 동작하는 것이기 때문에 pop()을 수행할 시 제거된 값을 뒤에서부터 순차적으로 매워줘야한다.
 
특히 위의 코드에선 항상 맨 앞에 값을 제거하는 pop(0)을 시행해주기 때문에 매번 리스트의 길이 - 1 만큼의 연산을 진행해줘야 할 것이다.
 
반면에 deque는 내부적으로 링크드 리스트로 구현되어 있기 때문에 pop연산을 상수 시간 내에 할 수 있다는 장점이 있다.