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

[프로그래머스] 풍선 터트리기 [월간 코드 챌린지 시즌1] [python] Level3

 

문제 설명

 

일렬로 나열된 n개의 풍선이 있습니다. 모든 풍선에는 서로 다른 숫자가 써져 있습니다. 당신은 다음 과정을 반복하면서 풍선들을 단 1개만 남을 때까지 계속 터트리려고 합니다.

1. 임의의 인접한 두 풍선을 고른 뒤, 두 풍선 중 하나를 터트립니다.
2. 터진 풍선으로 인해 풍선들 사이에 빈 공간이 생겼다면, 빈 공간이 없도록 풍선들을 중앙으로 밀착시킵니다.

여기서 조건이 있습니다. 인접한 두 풍선 중에서 번호가 더 작은 풍선을 터트리는 행위는 최대 1번만 할 수 있습니다. 즉, 어떤 시점에서 인접한 두 풍선 중 번호가 더 작은 풍선을 터트렸다면, 그 이후에는 인접한 두 풍선을 고른 뒤 번호가 더 큰 풍선만을 터트릴 수 있습니다.

당신은 어떤 풍선이 최후까지 남을 수 있는지 알아보고 싶습니다. 위에 서술된 조건대로 풍선을 터트리다 보면, 어떤 풍선은 최후까지 남을 수도 있지만, 어떤 풍선은 무슨 수를 쓰더라도 마지막까지 남기는 것이 불가능할 수도 있습니다.

일렬로 나열된 풍선들의 번호가 담긴 배열 a가 주어집니다. 위에 서술된 규칙대로 풍선들을 1개만 남을 때까지 터트렸을 때 최후까지 남기는 것이 가능한 풍선들의 개수를 return 하도록 solution 함수를 완성해주세요.

 

입출력 예 설명

입출력 예 #1

• 첫 번째 풍선(9가 써진 풍선)을 최후까지 남기는 방법은 다음과 같습니다.
  1. [9, -1, -5] 에서 -1, -5가 써진 풍선을 고른 뒤, -1이 써진 풍선(번호가 더 큰 것)을 터트립니다.
  2. [9, -5] 에서 9, -5가 써진 풍선을 고른 뒤, -5가 써진 풍선(번호가 더 작은 것)을 터트립니다.
• 두 번째 풍선(-1이 써진 풍선)을 최후까지 남기는 방법은 다음과 같습니다.
  1. [9, -1, -5] 에서 9, -1이 써진 풍선을 고른 뒤, 9가 써진 풍선(번호가 더 큰 것)을 터트립니다.
  2. [-1, -5] 에서 -1, -5가 써진 풍선을 고른 뒤, -5가 써진 풍선(번호가 더 작은 것)을 터트립니다.
• 세 번째 풍선(-5가 써진 풍선)을 최후까지 남기는 방법은 다음과 같습니다.
  1. [9, -1, -5] 에서 9, -1이 써진 풍선을 고른 뒤, 9가 써진 풍선(번호가 더 큰 것)을 터트립니다.
  2. [-1, -5] 에서 -1, -5가 써진 풍선을 고른 뒤, -1이 써진 풍선(번호가 더 큰 것)을 터트립니다.
• 최후까지 남을 수 있는 풍선은 9,-1,-5입니다.
• 3개의 풍선이 최후까지 남을 수 있으므로, 3을 return 해야 합니다.

입출력 예 #2

• 최후까지 남을 수 있는 풍선은 -16, -92, -71, -68, -61, -33이 써진 풍선으로 모두 6개입니다.

설계 및 구현

 

접근방법

1. 처음과 끝의 값은 끝까지 남길 수 있다.

2. 가운데 값은 left = 첫 번째 값, right = 마지막값  으로 출발하여 자기보다 작은수를 남길 수 있다.

   작은수를 발견할때마다 자기자신을 갱신하면서 끝까지 간다. *밑의 그림을 참고*

**입출력 예2** 에서 마지막까지 남을 수 있는 값들의 수를 구하는 과정

left에 갱신됬던 값들 = [-92]

right에 갱생됬던 값들 = [-61, -68, -71, -92]

answer = len([-92]) + len([-61, -68, -71, -92]) + 2(양 끝 값 갯수) - 1(중복된 값[-92]의 갯수)

이런 식으로 답을 구할 수 있다.

 

my_solution

def solution(a):
    answer = 2
    
    if 0 <= len(a) <= 2:
        return len(a)

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

코드를 보면 1

1. 양쪽 끝의 두개의 값은 무조건 남길 수 있으니 answer에 2를 저장해둔다.

2. a값의 개수가 0 <= len(a) <= 2 일 경우에는 가운데 값이 존재 하지 않으니 길이를 리턴 해서 해결

3. left,right에 각각 처음값과 마지막값을 저장한다.

4. a를 순회한다.

    ①left보다 작은수가 발견될 경우 left의 값을 더 작은수로 갱신하고 answr +=1 해준다

    ②right보다 작은수가 발견될 경우 right의 값을 더 작은수로 갱신하고 answr +=1 해준다

5. 마지막으로 가장 작은수는 중복이 됬는지 left == right로 검사를 하고 

    같다면 중복이 된 경우니 answer -= 1 을 한후 반환하여 해결 할 수 있다.!

  ex) 위의 예시 그림에서는 -92가 중복된다.

 

문제 설명만 보고는 바로 규칙이 떠오르지 않는 꽤나 어려운 문제였다...~