Python

문제 링크 https://www.acmicpc.net/problem/18352 문제 해설 Idea BFS 시작 노드 X부터 연결된 노드를 순차적으로 방문하면서 X로부터 떨어진 거리를 기록 거리가 K와 같은 노드를 출력하고, 해당하는 노드가 없을 경우 -1을 출력 거리가 K를 넘어가지 않는 노드에 대해서만 탐색하여 시간 단축 Time Complexity BFS: O(N+M) = 1,300,000 Data Size N: 2 <= int <= 300,000 M: 1 <= int <= 1,000,000 K: 1 <= int <= 300,000 X: 1 <= int <= N A, B: 1 <= int <= N 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 from collections import deque import sys input = sys....

문제 링크 https://www.acmicpc.net/problem/1495 문제 해설 Idea Dynamic Programming P[i] = max(P[i-1]+V[i-1],P[i-1]-V[i-1]), 0 <= P[i] <= M 모든 P[i-1]가 P[i+1]에 영향을 줄 수 있기 때문에 범위 내 모든 값을 집합에 저장 마지막 곡에 대한 P가 존재할 경우 최댓값을 출력하고, 없을 경우 -1을 출력 Time Complexity DP: O(NM) = 50,000 Data Size N: 1 <= int <= 50 M: 1 <= int <= 1,000 S: 0 <= int <= M V: int * N 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 N, S, M = map(int, input()....

문제 링크 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....