스킬트리
문제
선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.
예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다.
위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다.
선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요.
풀이
def solution(skill, skill_trees):
from collections import deque
answer = 0
while skill_trees:
learned = True
deq = deque(list(skill))
learn=[]
skill_tree = skill_trees.pop()
for i in skill_tree:
if i in skill:
learn.append(i)
for j in range(len(learn)):
if learn[j] != skill[j]:
learned = False
break
if learned == True:
answer += 1
return answer오늘 알고리즘 강의를 들으면서 배웟던
스택, 큐를 최대한 이용해서 풀어보려고 deque를 사용해서 풀었습니다
deque를 사용해 deq에 skill을 리스트로 넣어주고
for 문을 사용해서 풀었습니다.
skill_tree = skill_trees.pop()pop을 이용해 여러개의 스킬트리중 가장 마지막 스킬을 가지고옴
for i in skill_tree:
if i in skill:
learn.append(i)스킬을 순서대로 배워야 하므로, for문을 이용해서
첫 스킬부터 시작해서 일치하는 스킬이 있으면 배운 스킬에 넣어줌
for j in range(len(learn)):
if learn[j] != skill[j]:
learned = False
break만약 순서가 일치 하지 않으면 False를 내보냄
푼 문제는 1문제고, 풀지 못한 문제가... 3문제
더 맵게
문제
매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.
섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
틀린 풀이
def solution(scoville, K):
answer = 0
sum_scoville = scoville[0]
scoville.sort()
for i in range(len(scoville)):
try:
sum_scoville = sum_scoville + scoville[i+1]*2
if sum_scoville >= K :
answer += 1
return answer
else:
answer += 1
except IndexError:
return -1
return answer일단 최대한 풀어보긴 했는데, 시간초과는 당연하고
통과못한 예제가 많아서 생각을 많이 했던 문제 ...
heapq를 이용해서 푸는 방법 말고는 시간초과를 해결할 수 없다는 글이 많았고,
이에 불만을 제기하는 분들이 많았습니다
python 문서에서 headq를 보고 풀긴 했지만,
시간초과를 제외한 예제 통과를 목적으로 풀고 있습니다
heapq 관련 python 공식 문서
조금밖에 못풀어서 아쉽긴한데,
오늘 배운 que를 이용해서 한문제라도 푼거에 의미를 둬야지
푸는 방법하나 더 알았으니 내일은 더 잘풀겟지
