[프로그래머스] 풍선 터트리기
문제 링크
https://programmers.co.kr/learn/courses/30/lessons/68646
문제 설명
-
서로 다른 숫자 리스트가 주어짐
-
임의의 인접한 숫자 중 큰 숫자만 지울 수 있음
-
한 번만 작은 숫자를 지울 수 있음
-
마지막으로 남길 수 있는 숫자의 개수 리턴
틀린 풀이
-
모든 숫자를 돌면서
-
왼쪽의 큰 숫자들을 모두 제거
-
오른쪽의 큰 숫자들을 모두 제거
-
왼쪽 < 가운데 > 오른쪽이면 불가능
-
나머지 가능
-
O(N^2) 이라 시간 초과
맞은 풀이
-
어차피 모두 서로 다른 수이기 때문에 모두 제거 가능
-
모두 제거하면 최솟값만 남음
-
왼쪽의 최솟값 < 현재 값 > 오른쪽의 최솟값 이면 안 됨
-
모든 수를 돌면서 최솟값을 갱신 & 가능한지 체크
-
한 번에는 DP가 안 되고 왼쪽, 오른쪽 나눠서 해야 됨
-
왼쪽, 오른쪽 중 하나라도 True 이면 가능
느낀 점
- 시간 초과가 났을 때 어떻게 시도해야 할지 감은 오는 것 같다
틀린 코드
from collections import deque
def solution(numbers):
if len(numbers) < 3:
return len(numbers)
answer = 0
for i in range(len(numbers)):
if possible(numbers, i):
answer += 1
return answer
def possible(numbers, i):
if i == 0 or i == len(numbers)-1:
return True
curr = numbers[i]
q = deque(numbers)
# left
while True:
n1 = q.popleft()
n2 = q.popleft()
if n2 == curr:
q.appendleft(n2)
q.appendleft(n1)
break
if n1 < n2:
q.appendleft(n1)
else:
q.appendleft(n2)
# right
while True:
n2 = q.pop()
n1 = q.pop()
if n1 == curr:
q.append(n1)
q.append(n2)
break
if n1 < n2:
q.append(n1)
else:
q.append(n2)
if q[0] < q[1] > q[2]:
return False
return True
맞은 코드
def solution(numbers):
# left
min_value = float('inf')
left = [True] * len(numbers)
for i in range(len(numbers)):
if numbers[i] > min_value:
left[i] = False
else:
min_value = numbers[i]
# right
min_value = float('inf')
right = [True] * len(numbers)
for i in range(len(numbers)-1, -1, -1):
if numbers[i] > min_value:
right[i] = False
else:
min_value = numbers[i]
answer = 0
for i in range(len(numbers)):
if left[i] or right[i]:
answer += 1
return answer
Author And Source
이 문제에 관하여([프로그래머스] 풍선 터트리기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@leehj8896/프로그래머스-풍선-터트리기
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
서로 다른 숫자 리스트가 주어짐
임의의 인접한 숫자 중 큰 숫자만 지울 수 있음
한 번만 작은 숫자를 지울 수 있음
마지막으로 남길 수 있는 숫자의 개수 리턴
-
모든 숫자를 돌면서
-
왼쪽의 큰 숫자들을 모두 제거
-
오른쪽의 큰 숫자들을 모두 제거
-
왼쪽 < 가운데 > 오른쪽이면 불가능
-
나머지 가능
-
O(N^2) 이라 시간 초과
맞은 풀이
-
어차피 모두 서로 다른 수이기 때문에 모두 제거 가능
-
모두 제거하면 최솟값만 남음
-
왼쪽의 최솟값 < 현재 값 > 오른쪽의 최솟값 이면 안 됨
-
모든 수를 돌면서 최솟값을 갱신 & 가능한지 체크
-
한 번에는 DP가 안 되고 왼쪽, 오른쪽 나눠서 해야 됨
-
왼쪽, 오른쪽 중 하나라도 True 이면 가능
느낀 점
- 시간 초과가 났을 때 어떻게 시도해야 할지 감은 오는 것 같다
틀린 코드
from collections import deque
def solution(numbers):
if len(numbers) < 3:
return len(numbers)
answer = 0
for i in range(len(numbers)):
if possible(numbers, i):
answer += 1
return answer
def possible(numbers, i):
if i == 0 or i == len(numbers)-1:
return True
curr = numbers[i]
q = deque(numbers)
# left
while True:
n1 = q.popleft()
n2 = q.popleft()
if n2 == curr:
q.appendleft(n2)
q.appendleft(n1)
break
if n1 < n2:
q.appendleft(n1)
else:
q.appendleft(n2)
# right
while True:
n2 = q.pop()
n1 = q.pop()
if n1 == curr:
q.append(n1)
q.append(n2)
break
if n1 < n2:
q.append(n1)
else:
q.append(n2)
if q[0] < q[1] > q[2]:
return False
return True
맞은 코드
def solution(numbers):
# left
min_value = float('inf')
left = [True] * len(numbers)
for i in range(len(numbers)):
if numbers[i] > min_value:
left[i] = False
else:
min_value = numbers[i]
# right
min_value = float('inf')
right = [True] * len(numbers)
for i in range(len(numbers)-1, -1, -1):
if numbers[i] > min_value:
right[i] = False
else:
min_value = numbers[i]
answer = 0
for i in range(len(numbers)):
if left[i] or right[i]:
answer += 1
return answer
Author And Source
이 문제에 관하여([프로그래머스] 풍선 터트리기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@leehj8896/프로그래머스-풍선-터트리기
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
어차피 모두 서로 다른 수이기 때문에 모두 제거 가능
모두 제거하면 최솟값만 남음
왼쪽의 최솟값 < 현재 값 > 오른쪽의 최솟값 이면 안 됨
모든 수를 돌면서 최솟값을 갱신 & 가능한지 체크
한 번에는 DP가 안 되고 왼쪽, 오른쪽 나눠서 해야 됨
왼쪽, 오른쪽 중 하나라도 True 이면 가능
- 시간 초과가 났을 때 어떻게 시도해야 할지 감은 오는 것 같다
틀린 코드
from collections import deque
def solution(numbers):
if len(numbers) < 3:
return len(numbers)
answer = 0
for i in range(len(numbers)):
if possible(numbers, i):
answer += 1
return answer
def possible(numbers, i):
if i == 0 or i == len(numbers)-1:
return True
curr = numbers[i]
q = deque(numbers)
# left
while True:
n1 = q.popleft()
n2 = q.popleft()
if n2 == curr:
q.appendleft(n2)
q.appendleft(n1)
break
if n1 < n2:
q.appendleft(n1)
else:
q.appendleft(n2)
# right
while True:
n2 = q.pop()
n1 = q.pop()
if n1 == curr:
q.append(n1)
q.append(n2)
break
if n1 < n2:
q.append(n1)
else:
q.append(n2)
if q[0] < q[1] > q[2]:
return False
return True
맞은 코드
def solution(numbers):
# left
min_value = float('inf')
left = [True] * len(numbers)
for i in range(len(numbers)):
if numbers[i] > min_value:
left[i] = False
else:
min_value = numbers[i]
# right
min_value = float('inf')
right = [True] * len(numbers)
for i in range(len(numbers)-1, -1, -1):
if numbers[i] > min_value:
right[i] = False
else:
min_value = numbers[i]
answer = 0
for i in range(len(numbers)):
if left[i] or right[i]:
answer += 1
return answer
Author And Source
이 문제에 관하여([프로그래머스] 풍선 터트리기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@leehj8896/프로그래머스-풍선-터트리기
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
from collections import deque
def solution(numbers):
if len(numbers) < 3:
return len(numbers)
answer = 0
for i in range(len(numbers)):
if possible(numbers, i):
answer += 1
return answer
def possible(numbers, i):
if i == 0 or i == len(numbers)-1:
return True
curr = numbers[i]
q = deque(numbers)
# left
while True:
n1 = q.popleft()
n2 = q.popleft()
if n2 == curr:
q.appendleft(n2)
q.appendleft(n1)
break
if n1 < n2:
q.appendleft(n1)
else:
q.appendleft(n2)
# right
while True:
n2 = q.pop()
n1 = q.pop()
if n1 == curr:
q.append(n1)
q.append(n2)
break
if n1 < n2:
q.append(n1)
else:
q.append(n2)
if q[0] < q[1] > q[2]:
return False
return True
def solution(numbers):
# left
min_value = float('inf')
left = [True] * len(numbers)
for i in range(len(numbers)):
if numbers[i] > min_value:
left[i] = False
else:
min_value = numbers[i]
# right
min_value = float('inf')
right = [True] * len(numbers)
for i in range(len(numbers)-1, -1, -1):
if numbers[i] > min_value:
right[i] = False
else:
min_value = numbers[i]
answer = 0
for i in range(len(numbers)):
if left[i] or right[i]:
answer += 1
return answer
Author And Source
이 문제에 관하여([프로그래머스] 풍선 터트리기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@leehj8896/프로그래머스-풍선-터트리기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)