[Python] 프로그래머스. 풍선 터트리기 (Level 3)

programmers.co.kr/learn/courses/30/lessons/68646

코딩테스트 연습 - 풍선 터트리기

어떻게 접근해야 할지 모르겠어서, 다른 블로그의 풀이를 참고했다.

velog.io/@pss407/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A468646-%ED%92%8D%EC%84%A0-%ED%84%B0%ED%8A%B8%EB%A6%AC%EA%B8%B0

[프로그래머스]#68646 풍선 터트리기

핵심은

1. 리스트의 맨 앞 / 맨 뒷값은 항상 남을 수 있다.

ex) [-3,-7,-5] 값이 있다면, 문제 조건상 어떻게든 -3과 -5를 남길 수 있다. 한 번은 번호가 큰 풍선을 터트릴 수 있기 때문.

 

2. 리스트 중간에 있는 값 = 자신 위치의 좌/우 리스트의 최솟값보다 작을 경우 살아남을 수 있다.

기본적으로 두 개의 풍선 중 큰 풍선을 터트려야 한다 == 현재 위치의 좌/우 최솟값보다 작다면 풍선은 마지막까지 살아남을 수 있다.

 

 

 

	import math
	def solution(a):
	# 맨 앞, 맨 뒷 풍선은 어떻게든 남길 수 있다.
	# 가운데에 있는 풍선은, 자신을 둘러싼 풍선의 최솟값보다 작다면 남을 수 있다.
	answer = 0
	left, right = math.inf, math.inf
	maps = [[0 for _ in range(len(a))] for _ in range(2)]
	# 인접한 풍선 중 번호가 큰 풍선을 터트린다.
	# 왼쪽 기준으로, 번호가 작은 풍선을 남기는 경우
	for i in range(len(a)):
	if left > a[i]:
	left = a[i]
	maps[0][i] = left
	# 오른쪽 기준으로, 번호가 작은 풍선을 남기는 경우
	for i in range(len(a)-1, -1, -1):
	if right > a[i]:
	right = a[i]
	maps[1][i] = right
	for i in range(len(a)):
	if a[i] <= maps[0][i] or a[i] <= maps[1][i]:
	answer += 1
	return answer

view raw [프로그래머스] 풍선 터트리기.py hosted with ❤ by GitHub