라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니다.
해외 공장에서는 향후 밀가루를 공급할 수 있는 날짜와 수량을 알려주었고, 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶습니다.
현재 공장에 남아있는 밀가루 수량 stock, 밀가루 공급 일정(dates)과 해당 시점에 공급 가능한 밀가루 수량(supplies), 원래 공장으로부터 공급받을 수 있는 시점 k가 주어질 때, 밀가루가 떨어지지 않고 공장을 운영하기 위해서 최소한 몇 번 해외 공장으로부터 밀가루를 공급받아야 하는지를 return 하도록 solution 함수를 완성하세요.
dates[i]에는 i번째 공급 가능일이 들어있으며, supplies[i]에는 dates[i] 날짜에 공급 가능한 밀가루 수량이 들어 있습니다.
제한조건
stock에 있는 밀가루는 오늘(0일 이후)부터 사용됩니다.
stock과 k는 2 이상 100,000 이하입니다.
dates의 각 원소는 1 이상 k 이하입니다.
supplies의 각 원소는 1 이상 1,000 이하입니다.
dates와 supplies의 길이는 1 이상 20,000 이하입니다.
k일 째에는 밀가루가 충분히 공급되기 때문에 k-1일에 사용할 수량까지만 확보하면 됩니다.
dates에 들어있는 날짜는 오름차순 정렬되어 있습니다.
dates에 들어있는 날짜에 공급되는 밀가루는 작업 시작 전 새벽에 공급되는 것을 기준으로 합니다. 예를 들어 9일째에 밀가루가 바닥나더라도, 10일째에 공급받으면 10일째에는 공장을 운영할 수 있습니다.
밀가루가 바닥나는 경우는 주어지지 않습니다.
입출력 예
stock
dates
supplies
k
result
4
[4,10,15]
[20,5,10]
30
2
입출력 예 설명
현재 밀가루가 4톤 남아 있기 때문에 오늘과 1일 후~3일 후까지 사용하고 나면 모든 밀가루를 다 사용합니다. 따라서 4일 후에는 반드시 밀가루를 공급받아야 합니다.
4일째 공급받고 나면 15일 이후 아침에는 9톤의 밀가루가 남아있게 되고, 이때 10톤을 더 공급받으면 19톤이 남아있게 됩니다. 15일 이후부터 29일 이후까지 필요한 밀가루는 15톤이므로 더 이상의 공급은 필요 없습니다.
따라서 총 2회의 밀가루를 공급받으면 됩니다.
나의 풀이
import heapq
def solution(stock, dates, supplies, k):
c=0
h=[]
s=0
while stock < k:
for i in range(s,len(dates)):
if stock >= dates[i]:
heapq.heappush(h,-supplies[i])
s =i+1
else:
break
stock -= heapq.heappop(h)
c += 1
return c
1. heapq에서 최대힙을 이용합니다. 2. stock이 k보다 작은 경우 while문을 실행합니다. 2-1. stock보다 작은 날짜들을 heapq에 넣습니다. 최대힙을 만들기 위해 -를 추가합니다. 2-2. heapq에서 가장 작은 값을 stock에서 뺍니다.(최대힙을 stock에 더하는 것) 2-3. 밀가루 공급받은 횟수를 1 추가합니다. 3. r를 리턴합니다.
from itertools import permutations
def solution(baseball):
a=list(permutations(range(1,10),3))
r=0
for i in a:
ans=i
c=0
for b in baseball:
st=0
ba=0
ch=list(map(int,(str(b[0]))))
for j in range(3):
if ans[j] == ch[j]:
st += 1
for k in ch:
if k in ans:
ba += 1
ba -= st
if b[1] == st and b[2] == ba:
c += 1
if c == len(baseball):
r += 1
return r
1. 1부터 9까지 중 숫자야구의 숫자가 될 수있는 것을 순열을 이용해 뽑습니다. 2. 해당 숫자가 baseball을 통해 숫자야구의 답이 될 수 있는지 확인합니다. 2-1. 스트라이크의 개수를 구합니다. 2-2. 볼의 개수를 구합니다. 볼의 개수를 구하는 것에 스트라이트도 포함되어 있기 때문에 스트라이크 개수를 뺍니다. 2-3. 스트라이크와 볼의 개수가 baseball의 개수와 같은지 확인합니다. 2-4. 각 baseball의 경우를 계산하고 c가 baseball의 길이와 같으면 숫자야구의 답이 될 수 있기 때문에 r에 1을 더합니다. 3. 순열에 대해 모두 검사하고 r을 리턴합니다.
카카오에 신입 개발자로 입사한 콘은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴파일하여 로그를 보니 대부분 소스 코드 내 작성된 괄호가 개수는 맞지만 짝이 맞지 않은 형태로 작성되어 오류가 나는 것을 알게 되었습니다. 수정해야 할 소스 파일이 너무 많아서 고민하던 콘은 소스 코드에 작성된 모든 괄호를 뽑아서 올바른 순서대로 배치된 괄호 문자열을 알려주는 프로그램을 다음과 같이 개발하려고 합니다.
용어의 정의
'(' 와 ')' 로만 이루어진 문자열이 있을 경우, '(' 의 개수와 ')' 의 개수가 같다면 이를 균형잡힌 괄호 문자열이라고 부릅니다. 그리고 여기에 '('와 ')'의 괄호의 짝도 모두 맞을 경우에는 이를 올바른 괄호 문자열이라고 부릅니다. 예를 들어, "(()))("와 같은 문자열은 균형잡힌 괄호 문자열 이지만 올바른 괄호 문자열은 아닙니다. 반면에 "(())()"와 같은 문자열은 균형잡힌 괄호 문자열 이면서 동시에 올바른 괄호 문자열 입니다.
'(' 와 ')' 로만 이루어진 문자열 w가 균형잡힌 괄호 문자열 이라면 다음과 같은 과정을 통해 올바른 괄호 문자열로 변환할 수 있습니다.
1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다. 3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다. 4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다. 4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다. 4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다. 4-3. ')'를 다시 붙입니다. 4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다. 4-5. 생성된 문자열을 반환합니다.
균형잡힌 괄호 문자열 p가 매개변수로 주어질 때, 주어진 알고리즘을 수행해 올바른 괄호 문자열로 변환한 결과를 return 하도록 solution 함수를 완성해 주세요.
매개변수 설명
p는 '(' 와 ')' 로만 이루어진 문자열이며 길이는 2 이상 1,000 이하인 짝수입니다.
문자열 p를 이루는 '(' 와 ')' 의 개수는 항상 같습니다.
만약 p가 이미 올바른 괄호 문자열이라면 그대로 return 하면 됩니다.
입출력 예
p
result
"(()())()"
"(()())()"
")("
"()"
"()))((()"
"()(())()"
입출력 예 설명
입출력 예 #1 이미 올바른 괄호 문자열 입니다.
입출력 예 #2
두 문자열 u, v로 분리합니다.
u = ")("
v = ""
u가 올바른 괄호 문자열이 아니므로 다음과 같이 새로운 문자열을 만듭니다.
v에 대해 1단계부터 재귀적으로 수행하면 빈 문자열이 반환됩니다.
u의 앞뒤 문자를 제거하고, 나머지 문자의 괄호 방향을 뒤집으면 ""이 됩니다.
따라서 생성되는 문자열은 "(" + "" + ")" + ""이며, 최종적으로 "()"로 변환됩니다.
입출력 예 #3
두 문자열 u, v로 분리합니다.
u = "()"
v = "))((()"
문자열 u가 올바른 괄호 문자열이므로 그대로 두고, v에 대해 재귀적으로 수행합니다.
다시 두 문자열 u, v로 분리합니다.
u = "))(("
v = "()"
u가 올바른 괄호 문자열이 아니므로 다음과 같이 새로운 문자열을 만듭니다.
v에 대해 1단계부터 재귀적으로 수행하면 "()"이 반환됩니다.
u의 앞뒤 문자를 제거하고, 나머지 문자의 괄호 방향을 뒤집으면 "()"이 됩니다.
따라서 생성되는 문자열은 "(" + "()" + ")" + "()"이며, 최종적으로 "(())()"를 반환합니다.
처음에 그대로 둔 문자열에 반환된 문자열을 이어 붙이면 "()" + "(())()" = "()(())()"가 됩니다.
나의 풀이
def solution(p):
def rightp(p): # 올바른 괄호 문자열인지 검사
pp=p
for i in range(len(p)//2+1):
pp=pp.replace('()','')
if len(pp) == 0:
return True
else:
return False
def uv(p): # u, v로 나누기
st=[]
for i in range(len(p)):
st.append(p[i])
if st.count('(') == st.count(')'):
return ''.join(st), p[i+1:]
if rightp(p) is True or p is '':
return p
u,v=uv(p)
if rightp(u) is True:
return u+solution(v)
else:
a='('+solution(v)+')'
for i,v in enumerate(u[1:-1]):
if v == '(':
a += ')'
else:
a += '('
return a
def rightp는 올바른 괄호 문자열인지 확인하는 함수입니다.
def uv는 문자열을 u, v로 나눠주는 함수입니다.
1. 문자열 p가 빈 문자열이거나 올바른 괄호 문자열인 경우 p를 리턴합니다. 2. 함수 uv를 통해 u, v를 나눕니다. 2-1. u가 올바른 괄호 문자열인 경우 v를 처음부터 반복합니다. 2-2. u가 올바른 괄호 문자열이 아닌 경우 v를 처음부터 반복하고 나머지 문자열의 괄호방향을 바꿉니다.
함수를 통해 재귀를 하는 방식입니다. 문제를 푸는 것보다는 이해하기가 어려운 것 같습니다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.
제한조건
number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
k는 1 이상 number의 자릿수 미만인 자연수입니다.
입출력 예
number
k
return
1924
2
94
1231234
3
3234
4177252841
4
775841
나의 풀이
def solution(number, k):
a=[]
for i,v in enumerate(number):
while a and a[-1] < v and k > 0:
a.pop()
k -= 1
if k == 0:
a += number[i:]
break
a.append(v)
if k > 0:
a=a[:-k]
return ''.join(a)
앞에서부터 큰 숫자를 만들어야 전체적으로 큰 숫자가 될 수 있습니다.
1. 문자열 number를 검사합니다. 2. 리스트 a에 원소가 있고 리스트 a의 마지막 값이 순회하는 v보다 작고 k가 0보다 크면 리스트 a의 마지막 원소를 제거하고 k를 1 줄입니다. 3-1. k가 0이면 리스트 a에 순회하는 뒤의 원소들을 추가해 리턴합니다. 3-2. 순회하는 v를 리스트 a에 추가합니다. 4. k가 0보다 크면 리스트 a의 뒤에서부터 k개를 자릅니다. 5. 리스트 a를 리턴합니다.