풍선 터뜨리기

 

https://school.programmers.co.kr/learn/courses/30/lessons/68646

프로그래머스

문제요약:

풍선들의 리스트가 있고 각 풍선들은 숫자가 할당되어있다, 인접한 풍선에서 큰것을 터뜨리고 작은것을 터뜨릴수 있는건 한번일때, 마지막에 남을수 있는 풍선의 숫자를 구하시오

 

소요시간:

20분

난이도3

 

1차 코딩:

def solution(a):
	ans = 2
	for i in range(1,len(a)-1):
		min1= min(a[:i])
		min2= min(a[i+1:])
		if max(min1,min2,a[i]) !=a[i]:
			ans +=1
	return ans

논리를 간단하게 구현한 1차 코딩 입니다. 

인접한 풍선에서 큰것만 터뜨리게 되면 결국 마지막엔 제일 작은 숫자를 가진 풍선이 남게 될것입니다.

이때 만약 어떠한 특정한 풍선이 살아 남을 수 있는지 없는지 알고 싶다면 그 특정 풍선을 제외하고 앞뒤로 리스트를 만들고 각 리스트의 최소값을 구한다음 만약 앞리스트의 최솟값, 특정한 풍선, 뒷자리의 최솟값 이 세 숫자 중 만약 본인이 제일 큰것이 아니라면(제일작은값이라면 큰것만터뜨리면 되고 두번째라면 작은것을 터뜨릴수 있는 한번의 기회를쓰면됨) 마지막에 남을 수 있기 때문에 다음과 같이 코딩 했습니다.

 

하지만이는 i 가 증가할때 마다 min함수가 두번씩 돌아야 함으로,    

 

import heapq as hp
def solution(a):
	ans = 2
	min1 = []
	min2 = a[1:]
	hp.heapify(min2)
	min2_left = []
	for i in range(1,len(a)-1):
		hp.heappush(min1,a[i-1])
		hp.heappush(min2_left,a[i])
		while min2_left and min2_left[0]==min2[0]:
			hp.heappop(min2)
			hp.heappop(min2_left)
		if max(min1[0],min2[0],a[i]) != a[i]:
			ans +=1
	return ans

다음과 같이 heap함수를 이용해 그때그때 min1의 최소값을 구해주었으며 , heap구조에서 최소값이 아닌 특정 수를 빼는 방법은 다음과 같이 빠지는 후보 list를 만든다음 이 리스트의 최솟값과 min2의 최솟값이 같을 때 빼주면 우선순위큐에서 최솟값이 아닌 특정수를 뺄수 있습니다.

 

다른사람 코드1 :

def solution(a):
    answer = 0
    left, right = float('inf'), float('inf')
    min_map = [[0, 0] for _ in range(len(a))]

    # 왼쪽 범위에서 최솟값 찾기
    for i in range(len(a)):
        if left > a[i]:
            left = a[i]
        min_map[i][0] = left

    # 오른쪽 범위에서 최솟값 찾기
    for i in range(len(a) - 1, -1, -1):
        if right > a[i]:
            right = a[i]
        min_map[i][1] = right

    # 찾은 최솟값 데이터를 가지고 기준 숫자의 양쪽이 모두 기준 숫자보다 작으면 answer += 1
    for i in range(len(a)):
        if a[i] <= min_map[i][0] or a[i] <= min_map[i][1]:
            answer += 1

    return answer

작성자는 알고리즘은 저와 똑같이 짜셨지만, 그때 그때 최솟값을 구할 필요없이 미리 두바퀴를 돌며 특정 부분까지의 최소값을 미리 구한 후, 비교만 해주었습니다. 

 

다른사람 코드2 :

def solution(a):
    answer = 1
    M = min(a)
    for _ in range(2):
        m = a[0]
        i = 1
        while m != M:
            if m >= a[i]:
                m = a[i]
                answer += 1
            i += 1
        a.reverse()
    return answer

비슷한 매커니즘에 더 간단한 코드입니다.

앞에서 부터 ,또 뒤에서부터 총 두바퀴를 돌았으며 각 첫번째항을 기본으로 놓고 최솟값이 갱신되는 횟수를 세 주었습니다.

아까 자신의 앞, 자신, 자신의 뒤 이 셋중 최대값만 아니면 된다고 했는데, 사실 전체에서 최솟값은 정해져 있고, 이 최솟값이 포함된 리스트의 최솟값은 항상 이 최솟값이기 때문에, 전체에서 최솟값을 기준으로 좌우만 살피면 되며, 이 최솟값을 포함하기 때문에 1에서 부터 시작하였습니다.