# 테페리넷

## 테페리넷

### 관리자 전용

ps:problems:programmers:68646

# 풍선 터트리기

ps
링크https://programmers.co.kr/learn/courses/30/lessons/68646
출처프로그래머스
문제 번호68646
문제명풍선 터트리기
레벨Level 3
분류

애드혹

시간복잡도O(n)
인풋사이즈n<=1,000,000
사용한 언어Python
해결날짜2020/12/07

## 풀이

• 생각만 하면 구현은 굉장히 간단한 문제
• 풍선들 중에서 가장 작은 번호를 가진 풍선만 남기는 것은 '큰풍선 터트리기'만 사용해서 터뜨릴수 있다.
• 따라서, 어떤 풍선 a[i]가 그보다 왼쪽에 있는 모든 풍선들보다 번호가 작다면, a[0:i+1]에서 가장 작은 번호가 a[i]니까
• a[0:i+1]에서 '큰풍선 터트리기'만 사용해서 a[i]를 남길 수 있다.
• a[i]보다 오른쪽에 있는 숫자들, a[i+1:]은 min(a[i+1:])만 남기고 나머지는 전부 '큰풍선 터트리기'만 사용해서 터트릴 수 있다.
• 그러면 a[i]과 min(a[i+1:])만 남는데, 이때는 '작은 풍선 터뜨리기'를 써서 a[i]만 남길 수 있다.
• 마찬가지 방법으로 a[i] > min(a[i+1:]) 일때도 a[i] 풍선만 남길수 있다.
• 따라서 답은 {a[i] < min(a[:i]) 인 i의 갯수} + {a[i] < min(a[i+1:]) 인 i의 갯수} - 1 이다
• 1을 빼는 이유는 전체 배열의 최소값인 a[i]는, 두군데에 다 포함되어 중복으로 카운트되기 때문이다.
• 이걸 일반적인 방식으로 코드를 작성하면 코드 1 - 일반적 코드 처럼 구현된다.
• walrus operator을 list comprehension 안에 사용하면 코드 2 - 컴팩트 코드 처럼 컴팩트해지기는 한데.. 가독성을 해치는 것이 아닌지 조심스럽다. 지금 보기에는 직관성이 좀 떨어지는 느낌인데, walrus operator를 사용하는 패턴들에 익숙하지 않아서일 수도 있어서. 나중에 이런 코딩 패턴이 흔히 사용되게 된다면 아무 문제 없을 수도 있고… 패턴 자체가 좀 지저분해서 흔히 사용될 일이 없을 수도 있고.. 그래서 개인적으로 이 스타일을 쓰는 것을 허용할지 말지 아직 고민중이다.
• 속도는 코드 1 보다 느리다
• 뭐 어차피 이렇게 쓴다면 아예 더 확 줄이는 것도 가능하다
• def solution(a):
min_lnum = min_rnum = float('inf')
return (len([(min_lnum := num) for num in a if num < min_lnum])
+ len([(min_rnum := num) for num in reversed(a) if num < min_rnum])
- 1)

## 코드

### 코드 1 - 일반적 코드

"""Solution code for "Programmers 68646. 풍선 터트리기".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/68646
- Solution link: http://www.teferi.net/ps/problems/programmers/68646
"""

INF = float('inf')

def solution(a):
answer = 0
min_num = INF
for num in a:
if num < min_num:
answer += 1
min_num = num

min_num = INF
for num in reversed(a):
if num < min_num:
answer += 1
min_num = num

return answer - 1

### 코드 2 - 컴팩트 코드

"""Solution code for "Programmers 68646. 풍선 터트리기".

Compact code using walrus operater in list comprehension.
- Problem link: https://programmers.co.kr/learn/courses/30/lessons/68646
- Solution link: http://www.teferi.net/ps/problems/programmers/68646
"""

INF = float('inf')

def solution(a):
answer = 0
min_num = INF
answer += len([(min_num := num) for num in a if num < min_num])
min_num = INF
answer += len([(min_num := num) for num in reversed(a) if num < min_num])
return answer - 1

## 토론

댓글을 입력하세요:
G B Q H N

ps/problems/programmers/68646.txt · 마지막으로 수정됨: 2021/01/21 16:27 저자 teferi

### 문서 도구 