Total

합승 택시 요금 (다익스트라)

[1753번] 최단경로 구하기 (다익스트라, 우선순위큐, 힙) 다익스트라 음수간선 X S 시작점부터 다른 모든 노드로 가는 최단거리 구하는 알고리즘 기출 : 음수간선이 없는데 시작점이 있고 최단거리 구하는 문제 원리 최단거리를 구할 노드에서 시작하여 karla.tistory.com from heapq import heappush, heappop def solution(n, s, a, b, fares): INF = int(1e9) answer = INF graph = [[] for _ in range(n + 1)] for f in fares: i, j, k = f graph[i].append((j, k)) graph[j].append((i, k)) def dijk(start): # s를 시작점으로하는 다익..

메뉴 리뉴얼 (조합)

from itertools import combinations from collections import Counter def solution(orders, course): answer = [] for c in course: temp = [] for order in orders: combi = combinations(sorted(order), c) temp += combi cnt = Counter(temp) if len(cnt) > 1: m = max(cnt.values()) for i in cnt: if cnt[i] >= 2 and cnt[i] == m: answer.append("".join(i)) answer.sort() return answer print(solution(["ABCFG", "AC"..

신규 아이디 추천 (문자열, 정규식)

def solution(new_id): answer = '' # 1 new_id = new_id.lower() # 2 for n in new_id: if n.islower() or n.isdigit() or n in ['-', '_', '.']: answer += n # 3 while ".." in answer: answer = answer.replace('..', '.') # 4 if answer[0] == '.': answer = answer[1:] if answer[-1] == '.': answer = answer[:-1] # 5 if len(answer) == 0: answer = 'a' # 6 if len(answer) >= 16: answer = answer[:15] # 7 if len(ans..

광고삽입 (누적합)

def str_to_int(time): # 시간 문자열 -> 숫자 변환 h, m, s = time.split(':') return int(h) * 60 * 60 + int(m) * 60 + int(s) def int_to_str(time): # 시간 숫자 -> 문자열 변환 h = time // 3600 h = '0' + str(h) if h < 10 else str(h) time = time % 3600 m = time // 60 m = '0' + str(m) if m < 10 else str(m) time = time % 60 s = '0' + str(time) if time < 10 else str(time) return h + ':' + m + ':' + s def solution(play_time..

순위검색 (해시, 딕셔너리)

info 최대 50,000, query 최대 100,000로 이중 for문 불가 조합으로 모든 경우의 수 키만들고 점수를 값으로 넣음 쿼리 잘라서 리스트 만들고 키, 점수 구분 키값 있으면 키 값에 따른 점수 리스트 조회 점수 리스트에서 이분 탐색으로 인덱스 찾음 ( 몇번째 인지) 점수 리스트 길이에서 찾은 인덱스 값 빼면 몇명인지 구할 수 있음 키 값 없으면 0명 from itertools import combinations from bisect import bisect_left def solution(info, query): answer = [] infoDict={} for x in info: xl = x.split(" ") info_key=xl[:-1] score =int(xl[-1]) for i ..

1,2,3 떨어뜨리기 (트리, 구현)

분석 1) 엣지 정보로 트리 리스트 생성 {1: [2, 3], 2: [4, 5], 3: [6], 4: [], 5: [7], 6: [8, 9, 10], 7: [], 8: [], 9: [], 10: []} 2) 리프노드에 떨어지는 숫자 갯수 카운트 리스트 생성 (leaf) 용도 : 순서 리스트 생성할 때 타겟값과 비교해서 몇바퀴 돌아야하는지 확인하기 위해 {4: 0, 7: 0, 8: 0, 9: 0, 10: 0} 3) 하위 인덱스 방향 관리 리스트 생성 (r) 용도 : 하위노드중 몇번째로 가는지 계산해서 가기 위해 {1: 0, 2: 0, 3: 0, 4: -1, 5: 0, 6: 0, 7: -1, 8: -1, 9: -1, 10: -1} 4) 리프노드 떨어지는 순서 리스트 생성 (order) 용도 : 리프노드 돌면..

파괴되지 않은 건물 (누적합, numpy)

""" 1 ≤ board의 행의 길이 (= N) ≤ 1,000 1 ≤ board의 열의 길이 (= M) ≤ 1,000 1 ≤ skill의 행의 길이 ≤ 250,000 """ import numpy as np def solution(board, skill): answer = 0 # 적의 공격 혹은 아군의 회복 스킬이 모두 끝난 뒤 파괴되지 않은 건물의 개수 n=len(board) m=len(board[0]) temp=[[0 for j in range(m+1)] for i in range(n+1)] for t,r1,c1,r2,c2,d in skill: tt= -d if t==1 else d temp[r1][c1]+=tt temp[r1][c2+1]-=tt temp[r2+1][c1]-=tt temp[r2+1][..

파괴되지 않은 건물 (누적합, 2차원 합배열)

""" 1 ≤ board의 행의 길이 (= N) ≤ 1,000 1 ≤ board의 열의 길이 (= M) ≤ 1,000 1 ≤ skill의 행의 길이 ≤ 250,000 """ def solution(board, skill): answer = 0 # 적의 공격 혹은 아군의 회복 스킬이 모두 끝난 뒤 파괴되지 않은 건물의 개수 n = len(board) m = len(board[0]) temp = [[0 for j in range(m + 1)] for i in range(n + 1)] for t, r1, c1, r2, c2, d in skill: tt = -d if t == 1 else d temp[r1][c1] += tt temp[r1][c2 + 1] -= tt temp[r2 + 1][c1] -= tt te..

주차 요금 계산 (구현)

def calTime(stime, etime): st, sm = map(int, stime.split(":")) et, em = map(int, etime.split(":")) mtemp = em - sm if mtemp < 0: et -= 1 em += 60 mtemp = em - sm ttemp = et - st minutes = ttemp * 60 + mtemp return minutes def solution(fees, records): # 1 ≤ records의 길이 ≤ 1,000 import math answer = [] # 차량 번호가 작은 자동차부터 청구할 주차 요금을 차례대로 정수 배열에 담아서 return # 차번호, 시간순 정렬 r = [] for i in records: r.appe..

양궁대회 (재귀)

from copy import deepcopy max_diff, max_board = 0, [] def solution(n, info): def dfs(ascore, lscore, cnt, idx, board): global max_diff, max_board if cnt > n: return if idx > 10: diff = lscore - ascore if diff > max_diff: board[10] = n - cnt max_board = board max_diff = diff return if cnt < n: board2 = deepcopy(board) board2[10 - idx] = info[10 - idx] + 1 dfs(ascore, lscore + idx, cnt + info[10 -..