Algorithm

[프로그래머스] 42586. 기능개발

Programmers - 42586. 기능개발 접근 그냥.. 큐에 넣고 한 턴에 한번씩 모든 index의 값 speed만큼 증가시키면서 0번 index가 100 이상이 되었을 때 한번에 몇 개 빼는지 기록. 간단쓰 from collections import deque def solution(progresses, speeds): deq = deque(progresses) deq_speed = deque(speeds) answer = [] while len(deq) != 0: for i in range(len(deq)): deq[i] += deq_speed[i] cnt = 0 while len(deq) > 0 and deq[0] >= 100: deq.popleft() deq_speed.popleft() cn..

[프로그래머스] 42584. 주식가격

Programmers - 42584. 주식가격 접근1 맘같아선 싹 다 리스트에 박아버리고 for문 돌리고 싶다. 한번 해볼까 def solution(prices): answer = [0]*len(prices) for i in range(len(prices)): for j in range(i): if answer[j] == 0: if prices[j] > prices[i]: answer[j] = i-j for i in range(len(answer) - 1): if answer[i] == 0: answer[i] = len(answer) - 1 - i return answer 네 당연히 잘 돌아가구요 존나 오래 걸립니다 접근2 from collections import deque def solution(pr..

[프로그래머스] 42583. 다리를 지나는 트럭

Programmers - 42583. 다리를 지나는 트럭 접근 트럭의 무게와, 다리에 올라가 있던 시간을 저장하는 길이가 2인 배열을 저장하는 deque를 생성. 하나씩 다리에 올려도 되는지 검사하고, 올리면서 무한반복 from collections import deque def solution(bridge_length, weight, truck_weights): # [0] = truck's weight / [1] = the seconds when the truck on the bridge. truck_list = deque([[truck, 0] for truck in truck_weights]) truck_on_bridge = deque([]) seconds = 0 while truck_list..

[프로그래머스] 42579. 베스트앨범

Programmers - 42579. 베스트앨범 접근 우선, set으로 장르의 종류를 파악(중복 제거) dictionary를 이용해 장르별 플레이 횟수, 장르별 index와 index에 따른 play 횟수를 sub-dictionary로 저장. {'classic': 1450, 'pop': 3100} {'classic': {0: 500, 2: 150, 3: 800}, 'pop': {1: 600, 4: 2500}} 같은 느낌으로. 그리고 총 play수가 가장 많은 장르부터, 곡의 play수가 가장 많은 2개를 뽑아 차례대로 저장시킴. ** 단, play수가 같은 곡은 index가 빠른 순서대로 저장.

[프로그래머스] 42577. 전화번호 목록

Programmers - 42577. 전화번호 목록 접근1 해시? 딕셔너리로 접근? set으로 접근? 고민 많이 했음. 2중 for문으로 처리하면 쉽겠지만, 당연히 시간초과 뜰 거고... 모든 phone_num의 원소마다 "1234"라면 1 12 123 1234 이렇게 모든 경우의 수를 따져서 그 숫자가 (자신 제외) phone_num에 있는지 조사 -> 성립. 대신, 이제 찾을 때 set에 넣어서 하면 될 듯? def solution(phone_book): set_book = set(phone_book) for phone in phone_book: number = "" for num in phone: number += num if number in set_book and number != phone: ..

[LeetCode] 1696. Jump Game VI

접근1 DP.. Top-Down 방식으로 재귀를 이용해 구현. i번째부터 점프를 시작할 때의 최대 score를 score[i] 라고 저장 (메모이제이션) 그렇게 score[0]을 구해가는 방법. class Solution: def maxResult(self, nums: List[int], k: int) -> int: lenOfnum = len(nums) # index 'i' 부터 시작했을 때의 최대 score score = {lenOfnum-1: nums[lenOfnum-1]} # end index부터 반대로 순회 def dp(i): a = score.get(i, None) if i + 1 == lenOfnum: return nums[lenOfnum-1] if a != None: retur..

[LeetCode] 97. Interleaving String

접근1 - 실패 (DP, List 이용) 일단 Topic을 보니.. DP가 들어있었는데.. DP 너무 어려워 ㅠ s3를 순회하며 s1과 s2 두 쪽 모두에 있는 알파벳을 맞닥뜨렸을 때 처리하는 게 관건일 듯. s1 = "aabbc" s2 = "abbcd" s3 = "aababbbccd" 잘 생각이 안 나서, discuss 쪽을 살짝 들여다봤음. https://leetcode.com/problems/interleaving-string/discuss/32076/Simple-Python-DP-solution 이거. 이런 경우, s3의 첫 index부터 s1에서 빼올지 s2에서 빼올지.. 두 경우 모두를 선택하여 모두 따져봐야 함. s3의 모든 문자를 순회하면서, s1과 s2의 현재 진행 위치를 저장하며 가면 ..

[LeetCode] 509. Fibonacci Number

접근 얘는... 딱히 설명할 필요가 없을듯 기본적인 피보나치 수열 문제! class Solution: def fib(self, n: int) -> int: num1 = 1 num2 = 1 temp = 0 if n == 0: return 0 if n == 1 or n == 2: return 1 for _ in range(n-2): temp = num1 + num2 num1 = num2 num2 = temp return num2