✅ 문제 풀이 - 프로그래머스
🎈 예산
부서 별 신청 금액이 담긴 배열 d와 전체 예산 budget이 담겨져 있을 때 최대 몇 개의 부서에 물품을 지원할 수 있는지 return 하는 문제
def solution(d, budget):
answer = 0
d.sort()
for i in d:
budget -= i
if budget < 0:
break
answer += 1
return answer< 풀이 과정 >
단순 구현 문제!
주어진 배열 d를 오름차순 정렬한 후, 앞에서 부터 하나씩 빼다가 주어진 budget을 초과하면 중단하도록 구현했다.
이때 과정이 끝날 때마다 부서 + 1 처리
🎈 기능개발
작업 진도가 적힌 배열 progresses와 작업 개발 속도가 적힌 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지 return 하는 문제
def solution(progresses, speeds):
answer = []
day = 0
while progresses:
if progresses[0] + speeds[0] >= 100:
day += 1
progresses.pop(0)
speeds.pop(0)
else:
for i in range(len(progresses)):
progresses[i] += speeds[i]
if day:
answer.append(day)
day = 0
answer.append(day)
return answer< 풀이 과정 >
중요한 것은 배포되는 날에 몇개의 기기가 배포되는지가 핵심.
while문으로 progresses가 없어질때까지 다음 과정을 반복한다.
- 맨 앞에 위치한 작업이 100보다 커지면 day를 + 1처리하고 두 배열에서 pop 진행.
- 작업이 아직 완료가 안된 경우, for문으로 현 작업 진도에 개발 속도를 더하고 day가 존재하면, answer에 추가한 후 reset한다.
- 마지막으로 작업이 끝난 것들에 대해 answer에 추가해주기
🎈 가장 큰 수
0 또는 양의 정수가 담긴 배열 numbers에서 순서를 재배치하여 만들 수 있는 가장 큰 수를 만들기
def solution(numbers):
numbers = list(map(str, numbers))
numbers.sort(key = lambda x: x*3, reverse = True)
answer = str(int(''.join(numbers)))
return answer< 풀이 과정 >
주어진 numbers 원소가 각각 1000이하이므로, 주어진 number를 문자열로 바꿔준 후 문자열 *3처리를 한다.
이렇게 하는 이유는 문자로 변경된 숫자간의 첫 자리의 대소 비교를 위해서다.
6 >> 666 , 10 >> 101010, 2 >> 222 로 변경되어 아스키코드로 크기 비교를 진행하면 6, 2, 1 순으로 내림차순 정렬된다.
🎈 최솟값 만들기
길이가 같은 배열 2개가 주어지고, 각 한 개씩 숫자를 곱해 최솟값을 만드는 문제
def solution(A,B):
answer = 0
A.sort()
B.sort(reverse = True)
for i in range(len(A)):
answer += A[i] * B[i]
return answer< 풀이 과정 >
두 배열 중 하나는 오름차순, 나머지는 내림차순을 진행해 for문을 돌며 각 인덱스에 위치한 원소끼리 곱한 값을 answer에 더해준다.
🎈 나머지 한 점
직사각형에서 3개의 점이 주어지고 나머지 한 점을 구하는 문제
def solution(v):
x = []
y = []
for i in v:
x.append(i[0])
y.append(i[1])
for i in x:
if x.count(i) == 2:
x = list(set(x))
x.remove(i)
for i in y:
if y.count(i) == 2:
y = list(set(y))
y.remove(i)
x.extend(y)
return x< 풀이 과정 >
v 배열에서 x, y 리스트에 각 원소를 추가해 주고, 각각 for문을 돌며 count 값이 2인 경우 set 전환 후 해당 카운팅이 2가 된 원소를 제거 한다.
🎈 운송 트럭
트럭의 최대 허용 무게 max_weight와 상품의 이름, 무게 정보가 담긴 스펙이 주어지고 운반하고자 하는 상품명이 주어질 때, 필요한 총 트럭 수를 구하는 문제
def solution(max_weight, specs, names):
answer = 1
product = {}
for name, weight in specs:
product[name] = int(weight)
total_weight = 0
for n in names:
total_weight += product[n]
if total_weight > max_weight:
answer += 1
total_weight = product[n]
return answer< 풀이 과정 >
단순하다고 생각했는데, 효율성에서 좀 걸린 문제
dictionary을 이용하여 메모리 공간을 더 줄여주었다.
✍️ dictionary 사용 이유?
-> 기본적으로 해시를 사용하기에 O(1)의 복잡도를 갖는다.
이후 다음 과정을 거쳐 구현하였다.
- specs의 정보를 name과 weight 변수로 지정하여 dic에 각각 key, value로 저장한다.
- total_weight로 max_weight와 비교하도록 변수를 만들었고 주어진 상품 이름 정보를 거치며 total_weight에 앞서 딕셔너리에 넣은 value를 더해준다. 만일 max값보다 크다면, 트럭을 교체하는 작업을 거친다.
🎈 카펫
빨간색, 갈색으로 이루어진 카펫에서 빨간색은 내부에만, 갈색은 외부에만 존재한다고 한다. 빨간색, 갈색 카펫의 수가 주어졌을 때 가로, 세로 길이를 구하는 문제
def solution(brown, red):
answer = []
carpet = brown + red
for width in range(carpet, 2, -1):
if carpet % width == 0:
height = carpet // width
if red == (width-2) * (height-2):
return [width, height]< 풀이 과정 >
수학적으로 접근하여 풀이하였다.
가로를 width, 세로를 height라 하면 주어진 brown 값은 2width + 2(height-2)로 구할 수 있고, red 값은 (width-2)(height-2)로 구할 수 있다.
red와 brown수를 더하면 나오는 값은 총 카펫 수. 즉 가로*세로의 값과 동일
가로가 세로보다 무조건 크거나 같으므로 for문을 역순으로 이용하여 carpet을 나눈 가로 값들을 구함.
이때 height는 carpet // width 임을 이용.
앞서 구했던 가로, 세로를 이용한 brown, yellow값을 적용하여 결과 return!
🎈 사탕 담기
가방이 감당할 수 있는 무게 m, 사탕 별 무게가 담긴 배열 weights가 주어졌을 때 정확하게 사탕들의 무게 합으로 m이 되도록 만드는 방법의 수를 구하는 문제 (단, 같은 사탕을 넣을 수 없다.)
def solution(m, weights):
answer = 0
n = len(weights)
dp = [[0]*(m+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(1, n+1):
for j in range(m+1):
dp[i][j] = dp[i-1][j]
if j >= weights[i-1]:
dp[i][j] += dp[i-1][j - weights[i-1]]
return dp[n][m]< 풀이 과정 >
문제를 보자마자 dp 혹은 재귀 탐색을 진행해야겠다는 생각을 했고, 주어진 m의 범위가 100000까지 이므로 dp가 더 효율적이라고 생각했다.
기존에 풀었던 knapsack 알고리즘과 유사하다고 생각이 들었고 이를 적용하였다.
dp[i][j] = i개의 사탕으로 j만큼의 무게를 만들 수 있는 수를 의미한다.
즉, i-1개로 j만큼의 무게를 만드는 경우의 수가 된다.
그리고, 무게 j가 주어진 weights보다 크거나 같다면, dp 개수는 기존에 값에 현 경우의 수를 더해준다.
결과적으로 dp의 오른쪽 아래 끝을 뽑아주면 되는 문제.
