네발로 코딩하는 포메라니안

1. 문제 2. 풀이 과정 방법 1) 시간 초과 number에서 k개를 뺏을 때 len(number) - k 길이의 수를 만들어야 한다. 이 조건에서 첫 번째 자리가 될 수 있는 수는 뒤에서 count 했을 때, 원하는 길이 이상인 값들이 그 후보이다. 최댓값과 그의 index값을 따로 찾는 데에 시간이 오래 걸렸다고 판단하였다. def solution(number, k): answer = '' pre_idx = -1 for i in range(1, len(number)-k+1)[::-1]: #이전에 선택한 값의 뒤부터 길이에 맞는 곳까지 중 최대값 찾기 answer += max(number[pre_idx+1:len(number)-i+1]) pre_idx = number[pre_idx+1:len(numb..

1. 문제 2. 풀이 과정 방법 1) 이진탐색을 사용한다. 최소값 즉, start = 0이고 최대는 가능한 n편의 최대가 배열의 길이이므로 end = l로 설정하였다. def solution(citations): citations.sort() l = len(citations) s = 0 e = l #최댓값 while s

1. 문제 2. 풀이과정 방법 1) heapq 내장 모듈 활용 import heapq def solution(scoville, K): answer = 0 heapq.heapify(scoville) while scoville[0] < K: if len(scoville) == 1: return -1 answer += 1 #가장 안매운거, 두 번째 안매운거 heap에서 빼서 연산 a = heapq.heappop(scoville) + heapq.heappop(scoville)*2 #섞은거 넣기 heapq.heappush(scoville, a) return answer 방법 2) heapq대신 deque만 이용하였다. 섞은 결과는 새로운 배열 mix에 따로 저장하여 scoville와 mix의 맨 앞 원소만 비교하..

1. 문제 2. 풀이 과정 방법 1) 직관적으로 생각나는 방법, 자신보다 뒤에 있는 값을 하나씩 확인해서 계산한다. 시간복잡도 O(%{n}^2%) def solution(prices): answer = [] for i in range(len(prices)): for j in range(i+1, len(prices)): if prices[i] > prices[j]: answer.append(j-i) break if len(answer)-1 < i: answer.append(len(prices)-1-i) return answer 방법 2) stack을 이용해서 더 빨리 계산한다. 코드 실행 과정 예시 입력 : [1, 2, 3, 2, 1] stack [(1, 0)] [(1, 0), (2, 1)] [(1, 0)..

1. 문제 2. 풀이과정 방법 1) 큐에 [트럭 무게, 위치]를 넣고, 반복문 한 번 돌 때마다 위치를 1 감소시켜서 위치 값이 1이 되면 트럭이 다리에서 나간다. 변수 c는 다음에 기다리는 트럭의 truck_weights에서의 인덱스 값을 나타낸다. from collections import deque def solution(bridge_length, weight, truck_weights): answer = 1 Q = deque() #다리 Q.append([truck_weights[0], bridge_length]) sum = truck_weights[0] c = 1 while Q: answer += 1 if Q[0][1] == 1:#다리 출발(bridge_length)에서 끝(1)까지 도착하면 po..

1. 문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 2. 풀이 과정 필요한 개념 : 조합, BFS 3개의 벽을 어디 세울지에 대해 조합을 사용하고, virus가 퍼지는 과정을 BFS를 통해 수행한다. 방법1) 재귀를 이용한 조합 import sys, copy, collections input = sys.stdin.readline n, m = map(int, input().split()) dx = [-1, 0, 1, 0] dy = [0, 1, 0, -..

1. 문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 2. 풀이 과정 import sys from collections import deque input = sys.stdin.readline n, m = map(int, input().split()) dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] q = deque() graph = [] for i in range(m): graph.append(list(..