프로그래머스

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42895 문제 해설 Idea Dynamic Programming S[1] = {N} S[2] = {NN, N+N, N-N, N*N, N/N} S[3] = {NNN, S[2] (+,-,*,/) S[1][y], …} 2부터 8까지의 범위를 가진 i와 1부터 i-1까지의 범위를 가진 j에 대해, S[j]와 S[i-j]의 사칙연산 결과를 S[i]에 추가하고 해당 집합이 number를 포함하는지 검증 Time Complexity DP: O(1) Data Size N: 1 <= int <= 9 number: 1 <= int <= 32,000 answer: int <= 8 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 from itertools import product def solution(N, number): S = [set() for _ in range(9)] if N == number: return 1 else: S[1]....

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/17686 문제 해설 Idea 정규표현식을 활용해 HEAD, NUMBER, TAIL을 분리 전체 파일명을 완전탐색하면서 리스트에 분리된 파일명을 저장 HEAD와 NUMBER를 기준으로 파일명을 정렬하고 정렬된 원본 파일명을 반환 Time Complexity Brute-Force + Sort: O(NM+NlogN)) = 110000 Data Size files: str(100) * 1000 해설 코드 1 2 3 4 5 6 7 8 9 10 11 import re def solution(files): answer = [] for file in files: head, number, tail = re....

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/17684 문제 해설 Idea LZW 알고리즘 (List로 구현) 단어를 문자 단위로 탐색하면서 캐시에 추가 캐시가 문자 사전에 없을 경우 이전 문자까지의 인덱스를 반환하고 캐시를 문자 사전에 추가 Time Complexity Brute-Force: O(N^2) = 1000000 Data Size msg: str(1000) 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 def solution(msg): answer = [] chars = [chr(x) for x in range(64,91)] cache = str() for c in msg: cache += c if cache not in chars: answer....

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/17683 문제 해설 Idea 악보 정보에서 #이 포함된 음을 소문자로 대체하고 완전탐색 시간 계산은 timedelta 활용 (재생시간,제목)으로 구성된 리스트를 정렬 Time Complexity Brute-Force: O(NM) = 143,900 Data Size m: 1 <= int <= 1439 musicinfos: list <= 100 musicinfos[0,1]: HH:MM (00:00 - 23:59) musicinfos[2]: str(64) musicinfos[4]: 1 <= int <= 1439 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 import datetime as dt import re import math def solution(m, musicinfos): answer = list() lower_repl = lambda match: match....

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/17680 문제 풀이 Idea LRU 알고리즘 (Deque로 구현) 도시이름이 캐시에 존재할 경우 시간에서 1 추가, 아닐 경우 5 추가 캐시에서 참고한 도시는 deque 최상단으로 재배치 캐시 사이즈를 초과할 경우 가장 오래된 도시를 제거 Time Complexity Deque: O(N) = 100,000 Data Size cacheSize: 0 <= int <= 30 cities: str(20) * 100,000 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 from collections import deque def solution(cacheSize, cities): answer = 0 cache = deque(maxlen=cacheSize) for city in cities: city = city....