프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.
또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.
먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.
*제한 사항
작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
작업 진도는 100 미만의 자연수입니다.
작업 속도는 100 이하의 자연수입니다.
배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.
문제 해결 방법
큐 구현을 위해 collections의 deque를 이용함
코드 구현
from collections import deque
def solution(progresses, speeds):
answer = []
progressesQ = deque()
speedsQ = deque()
cnt = 0
for i in range(len(progresses)):
progressesQ.append(progresses[i])
speedsQ.append(speeds[i])
while(1):
if progressesQ[0]>=100:
for i in range(len(progressesQ)):
if progressesQ[i] >= 100:
cnt+=1
else:
break
answer.append(cnt)
for i in range(cnt):
progressesQ.popleft()
speedsQ.popleft()
cnt = 0
if(len(progressesQ)==0):
break
for i in range(len(progressesQ)):
progressesQ[i] += speedsQ[i]
return answer
"죠르디"는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다.
게임 화면은 "1 x 1" 크기의 칸들로 이루어진 "N x N" 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 "5 x 5" 크기의 예시입니다). 각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다. 모든 인형은 "1 x 1" 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다. 게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인형은 바구니에 쌓이게 되는 데, 이때 바구니의 가장 아래 칸부터 인형이 순서대로 쌓이게 됩니다. 다음 그림은 [1번, 5번, 3번] 위치에서 순서대로 인형을 집어 올려 바구니에 담은 모습입니다.
만약 같은 모양의 인형 두 개가 바구니에 연속해서 쌓이게 되면 두 인형은 터뜨려지면서 바구니에서 사라지게 됩니다. 위 상태에서 이어서 [5번] 위치에서 인형을 집어 바구니에 쌓으면 같은 모양 인형 두 개가 없어집니다.
크레인 작동 시 인형이 집어지지 않는 경우는 없으나 만약 인형이 없는 곳에서 크레인을 작동시키는 경우에는 아무런 일도 일어나지 않습니다. 또한 바구니는 모든 인형이 들어갈 수 있을 만큼 충분히 크다고 가정합니다. (그림에서는 화면표시 제약으로 5칸만으로 표현하였음)
게임 화면의 격자의 상태가 담긴 2차원 배열 board와 인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열 moves가 매개변수로 주어질 때, 크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수를 return 하도록 solution 함수를 완성해주세요.
[제한사항]
board 배열은 2차원 배열로 크기는 "5 x 5" 이상 "30 x 30" 이하입니다.
board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다.
0은 빈 칸을 나타냅니다.
1 ~ 100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나타냅니다.
moves 배열의 크기는 1 이상 1,000 이하입니다.
moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.
인형의 처음 상태는 문제에 주어진 예시와 같습니다. 크레인이 [1, 5, 3, 5, 1, 2, 1, 4] 번 위치에서 차례대로 인형을 집어서 바구니에 옮겨 담은 후, 상태는 아래 그림과 같으며 바구니에 담는 과정에서 터트려져 사라진 인형은 4개 입니다.
문제 해결 방법
스택 자료구조를 이용하여 문제를 해결하였음
코드 구현
def solution(board, moves):
#시간 복잡도는 O(N^3)까지 가능함.
answer = 0
# 바구니의 크기는 무한대
basket = []
cnt=0
for move in moves:
for i in board:
if i[move-1] != 0: #만약 i 줄 배열에 move칸에 값이 0이 아니라면
try: # 바스켓이 비었을 때, pop하는 것을 방지하기 위함
a=basket.pop() # 바구니에서 뽑아서 현재 넣을 것과 비교
if a == i[move-1]: # 공통된다면 지우고 카운트 증가 시키기
cnt+=2
i[move-1] = 0
else:
basket.append(a)
basket.append(i[move-1]) # 바구니에 추가해줌
i[move-1] = 0 # 바구니에 추가한 것은 0으로 처리함
except: #만약 바스켓이 비어있다면? 예외구문으로
basket.append(i[move-1]) # 바구니에 추가해줌
i[move-1] = 0 # 바구니에 추가한 것은 0으로 처리함
break # 해당 반복문 탈출 후, 다음 move조회
else:# 만약 0이면
continue # 다음 줄로 넘겨서 조회함
return cnt
초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.
제한사항
prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
prices의 길이는 2 이상 100,000 이하입니다.
입출력 예
pricesreturn
[1, 2, 3, 2, 3][4, 3, 1, 1, 0]
입출력 예 설명
1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.
문제 해결 방법
아 이문제는 참 어렵다! 시간 복잡도는 O(N^2)에 맞추면 안되고 O(NlogN)까지 가능하다.
그런데 이 문제 아무리생각해봐도 O(NlogN)로 풀기 어려웠다. 그래서 O(N^2)로 풀어봤는데,,, 끝이 안난다.
이조건 맞추면 저 조건 안맞고, 저 조건 맞추면 이 조건 안맞고 그랬다.
그래서 결국 답을 보고 이해했다.
이 문제는 효율성을 해결하기 위해서는 반드시 스택으로 풀어야한다. 그런데 이 문제 스택을 어디에 적용할지 떠올리기가 참 어렵다.
코드 주석으로 설명하였다.
코드 구현
기존 코드 - 미해결
def solution(prices):
#O(N)으로 구현
answer = []
prices=list(prices)
stackk=[]
newPrices=[]
newPrices = list(prices)
for i in range(len(prices)):
if i == 0:
stackk.append(prices[i])
else:
newPrices.reverse()
if len(newPrices)==0:
break
newPrices.pop()
newPrices.reverse()
cnt=0
#print('prices[i]', prices[i-1], 'newPrices', newPrices)
for price in newPrices:
#print('price', price)
if prices[i-1]<=price:
cnt+=1
answer.append(cnt)
answer.append(0)
#print(answer)
return answer
개선 코드 - 해결
def solution(prices):
answer = []
total = len(prices)
answer = [0] * total
#각 초 시점의 길이를 넣을 배열
stackk = [0]
# 스택을 0으로 초기화 한 이유는 순회를 인덱스 1부터 하기 위해서임
# prices의 0번 인덱스는 스택에 넣고 시작한다.
for i in range(1, total):
# 1부터 total까지 순회한다.
# 0번 인덱스부터 total 인덱스까지 순회할 때, 가격의 증가만 있다면,
# 계속 stackk에 넣는다.
# 만약 가격이 떨어진다면 그때부터는 스택에서 꺼내어서 하락한 가격의 인덱스로부터 길이를 구한다.
while stackk and prices[stackk[-1]]>prices[i]:
a=stackk.pop()
answer[a]=i-a
stackk.append(i)
while stackk: # 스택이 빌 때까지 순회하여 길이를 찾아준다.
#이 스택은 최종적으로 증가한 값들만 남아있다.
a=stackk.pop()
answer[a]=total-a-1
#print(answer)
return answer
짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.
예를 들어, 문자열 S = baabaa 라면
b aa baa → bb aa → aa →
의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.
제한사항
문자열의 길이 : 1,000,000이하의 자연수
문자열은 모두 소문자로 이루어져 있습니다.
입출력 예
sresult
baabaa1
cdcd0
입출력 예 설명
입출력 예 #1
위의 예시와 같습니다.
입출력 예 #2
문자열이 남아있지만 짝지어 제거할 수 있는 문자열이 더 이상 존재하지 않기 때문에 0을 반환합니다.
문제 해결 방법
주어진 str을 list로 바꿔서 list 요소를 순회시킨다.
스택으로 쓸 배열을 하나 만든다.
첫번째 요소는 스택에 넣고,
두번째 요소부터는 스택에 있는 값을 꺼내어 비교한 후 같으면 아무 동작하지 않고 넘어간다.
만약 같지 않으면, 꺼낸 값을 스택에 다시 넣고, 현재 보고있는 list 요소도 스택에 같이 넣는다.
순회가 끝나고, 스택의 길이를 재봤을때, 길이가 0이면 1을 반환, 길이가 0보다 크면 0을 반환한다.
코드 구현
def solution(s):
#O(nLogN)으로 구현
stakk =[]
newS=s
newS=list(newS)
for i in range(len(newS)):
if i == 0 or len(stakk)==0:
stakk.append(newS[i])
else:
a = stakk.pop()
if newS[i] == a:
continue
else:
stakk.append(a)
stakk.append(newS[i])
if len(stakk)==0:
return 1
else:
return 0
만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.
대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.
제한사항
s의 길이는 1 이상 1,000 이하입니다.
입출력 예
sresult
"[](){}"3
"}]()[{"2
"[)(]"0
"}}}"0
입출력 예 설명
입출력 예 #1
다음 표는 "[](){}" 를 회전시킨 모습을 나타낸 것입니다.
xs를 왼쪽으로 x칸만큼 회전올바른 괄호 문자열?
0"[](){}"O
1"](){}["X
2"(){}[]"O
3"){}[]("X
4"{}[]()"O
5"}[](){"X
올바른 괄호 문자열이 되는 x가 3개이므로, 3을 return 해야 합니다.
입출력 예 #2
다음 표는 "}]()[{" 를 회전시킨 모습을 나타낸 것입니다.
xs를 왼쪽으로 x칸만큼 회전올바른 괄호 문자열?
0"}]()[{"X
1"]()[{}"X
2"()[{}]"O
3")[{}]("X
4"[{}]()"O
5"{}]()["X
올바른 괄호 문자열이 되는 x가 2개이므로, 2를 return 해야 합니다.
입출력 예 #3
s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.
입출력 예 #4
s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.
문제 해결 방법
문제가 스택 자료구조로 풀어야 할 문제임에도 불구하고, 스택으로 풀 생각을 구체적으로 하지않고 그냥 단순히 함수만 쓸 생각으로 코드를 짰다. 아니나 다를까 문제는 거진 통과인데 제일 마지막 테스트케이스에서 딱 멈췄다.
아~~ 테스트케이스를 추가하고 나서 어떻게 풀지 다시 생각해봤다.
추가한 테스트 케이스는 다음과 같다.
마지막 테스트 케이스를 풀기위해서는.. 아무리 생각해봐도 ... 스택적으로 문제를 풀 방법이 없다는 것을 깨달았다...
코드를 전면 수정했다. 기존 코드는 싹 지우고 다시 시작했다.
주어진 string을 순회 시키고,
각 string에서 한자 한자씩 읽는다.
(, {, [ 를 왼쪽 괄호라고 부르겠다. 배열 하나를 새로 만들고
왼쪽 괄호가 나오면 그 배열에 왼쪽 괄호를 PUSH 한다.
), }, ] 가 나오면 그 배열에서 POP한 것과 읽고 있는 글자가 같으면 넘어가고 카운트 한다
만약 글자가 같지 않으면 올바르지 않은 괄호 문자열이라고 판단한다.
코드 구현
개선된 코드
def solution(s):
left1 = []
left2 = []
left3 = []
check = [0]*3
pass1=0
pass2=0
for i in s:
if i == '(':
check[0]+=1
elif i == '[':
check[1]+=1
elif i == '{':
check[2]+=1
elif i ==')':
check[0]-=1
elif i == ']':
check[1]-=1
elif i == '}':
check[2]-=1
if check[0] ==0 and check[1]==0 and check[2]==0:
pass1=1
mylist=list(s)
if pass1==0:
return 0
else:
thisis = 0
for i in range(len(s)):
stakk = []
word = mylist.pop()
mylist.insert(0, word)
#print(mylist)
#print("---")
breakk=0
for i in mylist:
#print(i)
if i == ']':
try:
word = stakk.pop()
if word == '[':
continue
else:
breakk=1
break
except:
breakk=1
break
elif i == ')':
try:
word = stakk.pop()
if word == '(':
continue
else:
breakk=1
break
except:
breakk=1
break
elif i == '}':
try:
word = stakk.pop()
if word == '{':
continue
else:
breakk=1
break
except:
breakk=1
break
elif i == '[':
stakk.append('[')
elif i == '(':
stakk.append('(')
elif i == '{':
stakk.append('{')
if len(stakk)==0 and len(stakk)==0 and len(stakk)==0 and breakk==0:
thisis+=1
return thisis
기존 코드
def solution(s):
left = [0] * 3
check = [0]*3
pass1=0
pass2=0
for i in s:
if i == '(':
check[0]+=1
elif i == '[':
check[1]+=1
elif i == '{':
check[2]+=1
elif i ==')':
check[0]-=1
elif i == ']':
check[1]-=1
elif i == '}':
check[2]-=1
if check[0] ==0 and check[1]==0 and check[2]==0:
pass1=1
mylist=list(s)
if pass1==0:
return 0
else:
thisis = 0
for i in range(len(s)):
left = [0] * 3
word = mylist.pop()
mylist.insert(0, word)
#print(mylist)
#print("---")
for i in mylist:
#print(i)
if i == ']':
left[0]-=1
elif i == ')':
left[1]-=1
elif i == '}':
left[2]-=1
elif i == '[':
left[0]+=1
elif i == '(':
left[1]+=1
elif i == '{':
left[2]+=1
if left[0]<0 or left[1]<0 or left[2]<0:
break
#print('left[0]', left[0], 'left[1]', left[1], 'left[2]', left[2])
if left[0]>=0 and left[1]>=0 and left[2]>=0:
thisis+=1
return thisis
캐릭터는 좌표평면의 (0, 0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5)로 이루어져 있습니다.
제한사항
dirs는 string형으로 주어지며, 'U', 'D', 'R', 'L' 이외에 문자는 주어지지 않습니다.
dirs의 길이는 500 이하의 자연수입니다.
입출력 예
dirsanswer
"ULURRDLLU"7
"LULLLLLLU"7
입출력 예 설명
입출력 예 #1
문제의 예시와 같습니다.
입출력 예 #2
문제의 예시와 같습니다.
문제 해결 방법
1. 우선 음수 좌표의 끝(-5,-5)를 (0,0)으로 생각하고 구현했다.
2. set() 함수를 통해 중복을 제거함
3. U,D,L,R은 조건문을 통해서 처리되게 하였고, 제한하는 영역을 벗어나면 돌아올 수 있게 해줌
4. 지나간 거리는 예를들어 하나의 거리를 왼쪽에서 오른쪽으로 지나든, 오른쪽에서 왼쪽으로 지나든 방향 상관이 없기 때문에 해당 부분을 잘 체크해주었음
코드 구현
개선한 코드
def solution(dirs):
answer = 0
c = [[0]*11 for _ in range(11)]
# 나는 (5, 5)에 있다. 거기서부터 시작한다.
arr=[]
now = [5, 5]
result = set()
for dir in dirs:
n1, n2 = now[0], now[1]
if dir == "U":
now[1]+=1
if now[1]==11:
now[1]=10
elif dir == "D":
now[1]-=1
if now[1]==-1:
now[1]=0
elif dir == "L":
now[0]-=1
if now[0]==-1:
now[0]=0
elif dir == "R":
now[0]+=1
if now[0]==11:
now[0]=10
xtox, ytoy = now[0], now[1]
if n1==xtox and n2==ytoy:
pass
else:
result.add((n1, n2, xtox, ytoy))
result.add((xtox, ytoy, n1, n2))
answer=len(result)/2
return answer
기존의 코드
def solution(dirs):
answer = 0
c = [[0]*11 for _ in range(11)]
# 나는 (5, 5)에 있다. 거기서부터 시작한다.
print(c)
arr=[]
now = [5, 5]
arr.append([5,5])
for dir in dirs:
if dir == "U":
now[1]+=1
if now[1]==11:
now[1]=10
elif dir == "D":
now[1]-=1
if now[1]==-1:
now[1]=0
elif dir == "L":
now[0]-=1
if now[0]==-1:
now[0]=0
elif dir == "R":
now[0]+=1
if now[0]==11:
now[0]=10
print(now)
one=now[0]
two=now[1]
c[one][two]=1
arr.append([one, two])
print(arr)
#중복제거를 먼저하고
#이전에 갖고있던 원소랑
cnt=0
for i in c:
cnt += i.count(1)
print("cnt:", cnt)
return answer
시간/공간 복잡도
O(N)
최적화 및 개선
처음에는 좌표만큼의 이차원 배열을 0으로 채워 구현하고 그 좌표를 지나면 좌표에 대한 자리를 1로 바꿔주었다. 그런데 문제 예시 1번과 2번의 케이스에 대해 답이 다르게 나왔다. 이 케이스를 공통적으로 해결하기 위해서는 반드시 어디에서 출발했는지도 포함이 되어야 답이 나오는 문제였다.
따라서 어떤 좌표에 도착했는지만 메기던 기존 코드에서 어디에서 출발했는지도 추가해서 4요소를 set을 통해서 추가하였다.
어려웠던 점
아직 내공이 부족하구나~ 혼자 힘으로 해결하는 것도 좋지만, 안되겠다 싶으면 빠르게 인정하고 배움의 자세로 바로 공부하고 다음에 또 도전하는 것이 나에게 더 좋은 방법인것 같다~ 고집 이제 안녕~
처음에는 for문 안에서 for문이 돌때 마다 도전한 사용자와 클리어하지 못한 사용자를 체크했었다.
이 부분에서 5, 9, 22번 테스트케이스에서 계속 시간초과가 났다.
이 문제를 해결하기 위해서 스테이지별로 도전하는 사용자의 수를 따로 체크하고, 실패한 사용자를 따로 체크해야했다.
코드 구현
통과한 코드
def solution(N, stages):
answer = []
# 도전
# 스테이지 별 도전자 수를 구함
challenger = [0] * (N+2)
for stage in stages:
challenger[stage] += 1
fails = { }
total = len(stages)
for i in range(1, N+1):
if challenger[i]==0:
fails[i] = 0
else:
fails[i] = challenger[i] / total
total=total-challenger[i]
#print(fails)
result = sorted(fails, key=lambda x: fails[x], reverse=True)
#값을 기준으로 키를 정렬해서 반환함
#print(result)
return result
이 부분에서 5, 9, 22번 테스트케이스에서 계속 시간초과가 났던 코드
def solution(N, stages):
# 실패율을 구하는 코드를 완성하라
# 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수
# 전체 스테이지의 개수 N
# 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages
# 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return
answer = []
start = 1
over_count = 0
target_count = 0
my_answer = { }
while(1):
if start > N:
break
for i in range(len(stages)):
if stages[i] == start: # 스테이지를 진행중인 사람
target_count += 1
over_count += 1
elif stages[i] > start: # 스테이지를 클리어 한 사람
over_count += 1
if target_count == 0:
my_answer[start] = 0
else:
my_answer[start] = target_count / over_count
#print(target_count, "/", over_count)
#print(my_answer)
over_count = 0
target_count = 0
start += 1
result = sorted(my_answer, key=lambda x : my_answer[x], reverse=True)
return result
시간/공간 복잡도
문제에서 200,000의 입력이 주어지므로써 이를 무난하게 통과하기 위해서는 NlogN의 시간복잡도가 나오는 알고리즘을 짜야 했다.
최적화 및 개선
개선을 위해서 코드짤 때 관점과 구현 방법을 바꿔야했다.
기존에는 사용자가 stages 배열을 를 구성하는 사용자들에 대해서 start 변수를 통해 순차적으로 스테이지를 증가시키고 stages 요소들을 돌면서 이를 넘겼느냐를 체크했다.
스테이지의 개수를 기준으로 도전하는 사용자와 실패한 사용자를 각각 반복문을 통해 메기면 굳이 이중 반복문을 사용하지 않아도됐다.
어려웠던 점
한번 코드를 작성하려고 생각한 구현 관점을 수정하기가 어려웠다.
이런 부분은 시간이 엄청 오래걸린다.
그리고 확실히 시간복잡도를 미리 고려하고 코드의 효율성을 잘 확인하고 구현할 생각을 해야할 것 같다.
문제를 어떻게 풀어야 겠다는 생각과 구현을 어떻게 해야하겠다는 생각은 다른 생각이고, 구현에 대한 생각을 굳이 하지 않았는데, 앞으로 문제 통과를 위해서 제대로 해야겠다는 생각이 든다.
XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.
이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.
제한사항
k는 1 이상 5,000 이하인 자연수입니다.
dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
dungeons의 가로(열) 길이는 2 입니다.
dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.
"최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
"최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.
입출력 예
kdungeonsresult
80[[80,20],[50,40],[30,10]]3
입출력 예 설명
현재 피로도는 80입니다.
만약, 첫 번째 → 두 번째 → 세 번째 던전 순서로 탐험한다면
현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
남은 피로도는 60이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 20입니다.
남은 피로도는 20이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30입니다. 따라서 세 번째 던전은 탐험할 수 없습니다.
만약, 첫 번째 → 세 번째 → 두 번째 던전 순서로 탐험한다면
현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
남은 피로도는 60이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30이므로, 세 번째 던전을 탐험할 수 있습니다. 세 번째 던전의 "소모 피로도"는 10이므로, 던전을 탐험한 후 남은 피로도는 50입니다.
남은 피로도는 50이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 10입니다.
따라서 이 경우 세 던전을 모두 탐험할 수 있으며, 유저가 탐험할 수 있는 최대 던전 수는 3입니다.
문제 해결 방법
1. dungeons에서 모두 나올 수 있는 순서에 대해 경우의 수를 순열로 뽑는다.
2. 리스트를 하나 만들고, 순열로 뽑은 모든 경우의 수에 대해서 조건을 따져가면서 던전에 방문한 횟수를 카운트 하여 최종적으로 카운트 한 수를 해당 리스트에 추가한다.
2-1. 위에서 말한 조건으로 각 던전의 최소 필요 피로도가 k와 같거나 커야지 던전에 방문할 수 있으니 해당하는 조건을 체크한다.
2-2. 만약 k가 특정 던전에 방문할 수 있다면 k에서 소모 피로도를 빼준다.
3. 2번에서 만든 리스트에서 max값을 구하여 출력한다.
코드 구현
from itertools import permutations
def solution(k, dungeons):
answer = -1
cpk=k
cases = list(permutations(dungeons, len(dungeons)))
checkList=[]
for i in range(len(cases)):
cpK=k
checkcheck = 0
for j in range(len(cases[i])):
if cpK >= cases[i][j][0]:
cpK = cpK - cases[i][j][1]
checkcheck += 1
else:
pass
if j == len(cases[i])-1:
checkList.append(checkcheck)
answer = max(checkList)
return answer
배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다. 예를 들면,
배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요.
제한사항
배열 arr의 크기 : 1,000,000 이하의 자연수
배열 arr의 원소의 크기 : 0보다 크거나 같고 9보다 작거나 같은 정수
입출력 예
arranswer
[1,1,3,3,0,1,1][1,3,0,1]
[4,4,4,3,3][4,3]
입출력 예 설명
입출력 예 #1,2
문제의 예시와 같습니다.
문제 해결 방법
stack을 이용하여 문제를 푼다. 1. stack 구실을 할 임의의 리스트를 하나 만든다.
2. arr의 원소를 순회하면서 임의의 리스트에 첫번째 원소를 push한다.
2-1. 첫번째 이후의 원소들은 임의의 리스트의 마지막에 push한 값을 pop을 통해 꺼낸다.
2-2. 2-1번을 통해 꺼낸 값과 현재 넣고자 하는 arr의 원소를 비교하여 값이 같으면 pass하고 같지 않으면 push 한다.
코드 구현
1. 효율성 통과하지 못한 코드
def solution(arr):
answer = []
# pivot 변수 = p
# 이전 pivot을 기억하는 변수 = pre_p
check = 0
pre_p = arr[0]
l=len(arr)
for i in range(1, len(arr)):
p = arr[i]
#print('p', p, 'pre_p', pre_p)
if pre_p == p:
pre_p = p
arr[i] = 10
# '-'를 세는 변수 = check
check+=1
else:
pre_p=p
for i in range(check):
arr.remove(10)
answer = arr
return answer
2. 효율성 통과한 코드
def solution(arr):
stack = []
for i in range(len(arr)):
if i == 0:
stack.append((arr[i]))
else:
top = stack.pop()
stack.append(top)
if arr[i]==top:
pass
else:
stack.append(arr[i])
return stack
시간/공간 복잡도
1. 효율성을 통과하지 못한 코드: O(N^2)
2. 효율성을 통과한 코드: O(N)
최적화 및 개선
처음에 효율성을 통과하지 못한 코드에 대해서 중첩 되지 않는 for문을 썼는데 왜 시간복잡도 효율성이 통과되지 않는지 이해가 안갔다. 혹시 내가 stack자료구조를 고려하지 않고 코드를 작성해서 그 부분에서 오류가 나는건가? 싶었다. 그래서 코드를 stack자료구조를 고려해서 리스트를 stack화 해서 코드를 짰다. 확실히 pop함수를 사용해서 그런가 편리하고 뒷처리를 해주지 않아도 되는 점이 깔끔하고 좋았다. 그리고 효율성에도 통과했다.
그렇다면 1번 코드는 어디에서 효율성을 많이 잡아먹는가?
바로 for문에 있는 remove함수 때문이다.
remove함수는 시간복잡도 O(N)을 잡아먹는다. 그런데 이걸 for문으로 처리하고있으니 시간복잡도가 O(N^2)이 되었던 것이였다.
어려웠던 점
파이썬 각각의 함수들의 특성에 대해서는 잘 몰랐는데, 이렇게 문제를 풀면서 기억에 각인도 시키고 하니 좋다.
어쩜 코딩테스트 문제들은 하나같이 문제 푸는 사람이 그 문제를 풀기위해서 알아야 하는것을 모른다면, 그것에 대해서 스스로 알게되지 않고서야 절대 문제를 못풀게끔 되어있는게 너무 신기하다. 이제야 드는 생각인데, 코딩테스트나 알고리즘 공부 어쩌면 좋은 제도일지도 모르겠다는 생각이 든다.
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
제한사항
numbers는 길이 1 이상 7 이하인 문자열입니다.
numbers는 0~9까지 숫자만으로 이루어져 있습니다.
"013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.
입출력 예
numbersreturn
"17"3
"011"2
입출력 예 설명
예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.
예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.
11과 011은 같은 숫자로 취급합니다.
문제 해결 방법
1. numbers 문자열을 문자로 떼내어 리스트에 정리한다.
2. 정리한 리스트를 permutations함수를 통해 각 원소들을 통해 만들 수 있는 조합 모든 경우(한자리, 두자리, 세자리 ,, numbers의 길이만큼의 자리)를 리스트에 정리한다.
3. 소수판별 함수를 만들어서 위의 리스트 원소들을 대상으로 소수 판별을 한다.
4. 결과 출력
코드 구현
from itertools import permutations
def solution(numbers):
answer = 0
numbers= str(numbers)
Nlist=[]
for i in range(len(numbers)):
Nlist.append(str(numbers[i]))
totalList = []
for i in range(len(numbers)):
if i == len(numbers):
break
totalList += list(map(''.join, (permutations(Nlist, i+1))))
totalList=list(map(int, totalList))
totalList=set(totalList)
totalList=list(totalList)
if 0 in totalList:
totalList.remove(0)
if 1 in totalList:
totalList.remove(1)
def primenumber(x):
# 2부터 x-1까지 순회
for i in range(2, x):
if x % i == 0:
# 하나라도 나눠 떨어지면 False 반환
return False
# 아무것도 나눠 떨어지는게 없으면 True 반환
return True
for i in range(len(totalList)):
if primenumber(totalList[i])== True:
answer+=1
# 어둠의 잔해 소수 판별기
# topic=2
# check=0
# for i in range(len(totalList)):
# while 1:
# if totalList[i] == 0:
# # 원소 0은 pass
# pass
# if totalList[i] % topic == 0:
# check+=1
# if check ==1:
# break
# topic+=1
# else:
# topic+=1
# if topic == totalList[i]:
# topic = 2
# break
# if check == 1:
# answer+=1
# check=0
# else:
# check=0
# pass
return answer
시간/공간 복잡도
O(N)
최적화 및 개선
하지않음
어려웠던 점
문제를 어떻게 풀어야하겠다는 것은 알겠지만서도, 자잘한 문법, 함수 사용법을 정확하게 몰라서 좀 시간이 걸렸다.
생각하는데로 출력하고 활용하는것이 좀 어려웠다.
특히 튜플 자료형, join함수, map함수, map객체, set함수 등에 대해서 잘 몰라서 새로 찾아봤다.
소수를 찾는 로직도 예전에 문제를 한번 풀어봤었는 경험으로 코드를 짜봤는데(어둠의 잔해 소수 판별기), 시간초과가 나왔다. 왜그럴까??? 빈틈없이 짰다고 생각했는데, 시간날때 다시 한번 봐야겠다.
