[프로그래머스]월간 코드 챌린지 시즌1- 풍선 터트리기, 파이썬

문제

---

• 프로그래머스 문제 링크

풀이

---

• 시간초과를 생각하지 않고 짜다 오래걸렸다(문제를 잘 읽고 풀자 ㅠ)
• 양 끝은 최후까지 남기는 것이 가능하다([1, 2] 라 했을 때 한 번 작은걸 터트릴 수 있는 기회로 1을 날려버리면 됨)
• 위 가정을 하기 위해서는 2개 남기기 전까지는 무조건 큰 수를 제거해야 함을 알 수 있다.
• 예시로 주어진 [-16, 27, 65, -2, 58, -92, -71, -68, -61, -33] 을 보자
• 따라서 27은 제거되어야 하기 때문에 양 극단이 될 수 없다 = -16보다 작은 수가 왼쪽 끝이 될 자격이 있고 오른쪽도 마찬가지 논리로 적용
• [-16, ~], [-92, ~], [~, -92], [~, -71], [~, -68], [~, -61], [~, -33] 이 가능하다.
• 양쪽 방향으로 더 작은수를 찾다보면 무조건 한 점(이 경우는 -92)에서 만나게 되므로 1을 빼주면 된다.

코드

---

def solution(a):
    answer = 2
    left, right = a[0], a[-1]
    for i in range(len(a)):
        if left > a[i]:
            answer += 1
            left = a[i]
        if right > a[-1-i]:
            answer += 1
            right = a[-1-i]
    return answer-1