풍선 터트리기

• 생각만 하면 구현은 굉장히 간단한 문제
• 풍선들 중에서 가장 작은 번호를 가진 풍선만 남기는 것은 '큰풍선 터트리기'만 사용해서 터뜨릴수 있다.
• 따라서, 어떤 풍선 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)

"""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

"""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