[Programmers] 스킬트리 / 멀쩡한 사각형 / 주식 가격 (python)

🌴 스킬트리

문제 링크

해결 전략

skill : 선행 스킬 순서
skill_trees : 유저들이 만든 스킬트리를 담은 배열

1. skill_tree의 각 원소에 대해 skill의 포함여부 판단, 스킬이 포함되지 않은 경우 -1을 return하므로 -1에 대해서는 skill로 count (X)
2. skill이 포함된 경우 temp[s]에 스킬명과 index 저장
3. 다음 두 조건을 동시에 만족하는 경우 answer+=1
   1. temp의 value 순서가 skill의 순서와 같고(temp value 오름차순)
   2. temp와 skill이 가진 값과 순서가 동일
4. 1) skill이 순서대로 있고, 2) 선행스킬 조건을 만족하는 경우 answer+=1
5. 최종 answer return

예를 들어,
skill이 "CBD", skill_trees가 ["BACDE", "CBADF", "AECB", "BDA"] 인 경우

list(temp.values())	sorted(list(temp.values()))	''.join(temp.keys())	skill[:len(temp)]	가능여부
[2, 0, 3]	[0, 2, 3]	CBD	CBD	X
[0, 1, 3]	[0, 1, 3]	CBD	CBD	O
[2, 3]	[2, 3]	CB	CB	O
[0, 1]	[0, 1]	BD	CB	X

Source Code

def solution(skill, skill_trees):
    answer = 0

    for st in skill_trees:
        temp = {}

        # skill 포함여부& index
        for i, s in enumerate(skill):
            if st.find(s) != -1:
                temp[s] = st.find(s) # 스킬명& index

        if list(temp.values()) == sorted(list(temp.values())) and \
        ''.join(temp.keys()) == skill[:len(temp)]:
            answer += 1
    return answer

---

🌴 주식 가격

문제 링크

해결 전략

prices : 초 단위로 기록된 주식가격이 담긴 배열

1. 각 초의 가격에 대해 주식가격이 떨어지는 시점 find.
2. 차례대로 현재& cnt초 후의 가격을 비교하여 가격이 떨어지는 시점의 초를,
3. 끝까지 가격이 떨어지지 않는 경우는 마지막 시점까지 걸린 초를 return

Source Code

def solution(prices):
    answer = []

    for i, p in enumerate(prices):
        cnt = 0
        for j in range(i, len(prices)):
            if p > prices[j]:
                cnt += 1
                break
            else:
                cnt += 1
        answer.append(cnt - 1)

    return answer

---

🌴 예산

문제 링크

해결 전략

w, h : 직사각형의 가로& 세로 길이

1. w, h의 최대공약수 g를 구하고, 가로 w//g, 세로 h//g인 직사각형을 고려함. 이는 둘의 최대공약수일 때 좌측상단과 우측하단으로 깔끔한 대각선이 그어지기 때문
2. 1.의 각 직사각형에서 빠지는(대각선에 걸치는) 사각형의 수는 w//g+h//g-1
3. 2.의 직사각형 수가 g번 반복되므로 2.의 결과 * g
4. 전체 직사각형 수(w*h) - 빠지는 직사각형(3.의 결과) retrurn

Source Code

import math

def solution(w, h):
    # 최대공약수
    g = math.gcd(w, h)

    # 빠지는 사각형 수
    minus = (w // g + h // g - 1) * g

    return w * h - minus # 남은 사각형 수

Reference

순서대로 풀었는데,, 왜 지금 들어가니까 순서가 뒤죽박죽인지ㅠ
암튼 레벨2로 넘어와따 !!!!!!!!!!!!!!!!!