23.03.22 파이썬 코딩 퀴즈#202 풍선 터트리기 (프로그래머스 스쿨)

이번 문제는 풍선 터트리기 문제이다.

임의의 인접한 두 풍선을 고른 뒤, 두 풍선 중 하나를 터트린다.

그 다음 빈 공간이 없도록 풍선을 다시 밀집시킨 후, 인접한 두 풍선을 고르게 되는데,

이 때, 다시 고른 두 풍선중에 번호가 더 작은 풍선을 터뜨리는 행위는 최대 1번만 할 수 있다. 그 이후에는 두 풍선을 고른 뒤 번호가 더 큰 풍선만을 터트릴 수 있다.

위 규칙으로 풍선을 터트리고 난 뒤, 최후까지 남기는 것이 가능한 풍선들의 개수를 return 해야 한다.

전달받는 a (풍선)의 길이는 1이상 백만 이하이며, a의 요소는 -10억 이상 10억 미만인 정수이고, 중복되지 않는다.

입출력 예 1을 먼저 살펴보자

방법이야 여러가지가 있겠지만, 남길 수 있는 수는 3개 모두 이다.

그리고 설명에서도 나오듯이 큰 수를 제거하는 횟수는 무제한이다. 즉 작은수만 제거하지 않는다면 언제나 큰 수를 제거할 수 있다.

입출력 예제2의 경우 별다른 설명없이 결과만 써져있다.

 

무언가 규칙이 있는것 처럼 보이는데, 입출력 예2를 좀 더 자세히 살펴보자.

먼저 그림으로 최후까지 남을 수 있는 풍선을 그려보면, 위 와 같다

최소값 -92를 기준으로 오른쪽의 수들은 모두 남을 수 있고, 왼쪽의 수는 단 하나의 최소값 -16만 남길 수 있다.

그 이유를 살펴보자.

먼저 -71을 남기는 방법은 간단하다. -92를 기준으로 왼쪽 값들은 큰값 기준으로 전부 제거한다.

그러면 이제 배열은 -92와 기준 오른쪽 배열이 남게 된다.

이때 -92,와 -71을 선택한 뒤 작은 값 -92를 제거한다.

한번 작은 값을 제거했기 때문에 자연스레 큰 값들만 제거 가능하며, 남은 값들 중 가장 작은 -71이 남게 된다.

-68을 남기는 방법은 설명이 한 줄 더 들어가지만 방법은 똑같다.

-92와 -71을 선택하여 큰 값 -71을 제거한다.

그 다음 -92와 -68을 선택하여 작은 값 -92를 제거한다. 그 이후에는 가장 작은 값 -68이 남게 된다.

-61을 남기려면 계속 큰 값들을 제거해 가다가, -92와 -61이 남았을 때 작은 값 -92를 제거해주면 된다.

-33을 남기는 방법 역시 동일하다. 즉 작은 값을 제거하는 시점에 따라 최소값 기준 오른쪽의 요소들은 전부 남길 수 있다.

 

이제 최소값 기준 왼쪽 배열을 살펴보자.

-16을 남기는 방법은 간단하다.

먼저 -92를 기준으로 큰 값을 제거하는 방법으로 오른쪽 배열을 전부 삭제해 준다.

그 다음 -16을 기 준으로 큰 값을 제거하는 방법으로 -92를 제외한 모든 요소를 제거해 준다.

이제 남은 -16과 -92중 작은 값 -92를 제거하면 -16이 남는다.

그렇다면 다른 값들은 왜 남길 수 없을까?

이유는 간단하다. 한쪽편을 제거하고 남긴 왼쪽 배열의 최소값은 -16이다.

최종적으로 -16과 -92를 제거하려면 두 값이 붙어야 하는데, 그 사이 존재하는 값들을 다 삭제해야만 가능하다.

index 0 과 index 4 만 위치 교환

만약 왼쪽 배열의 초소값과 전체 배열의 최소값이 붙어 있다면 어떻게 될까?

일단 -2는 위 방법으로 남길 수 있다.

그다음 왼쪽 배열의 최대값 65를 남기고 싶지만, 딱히 방법이 없어 보인다.

일단 규칙대로 65와 -92를 남기기 위해 그 사이 값들은, -92와 같이 뽑아서 큰 값을 제거하는 방법으로 제거 가능하다.

하지만 65기준 왼쪽배열의 경우 65를 남기기 위해서는 필연적으로 작은값을 한번은 제거해야 한다.

하지만 이렇게 작은 값을 한번 제거하면 65와 -92이 남더라도, 규칙에 의해 -92를 제거하지 못한다.

하지만 65와 27을 선택해 큰값 65를 제거하고 그 다음 작은값 -92를 제거하면 27은 남길 수 있다.

58 역시 같은 방법으로 남기는게 가능하다.

 

다시 오른쪽 배열을 살펴보자.

같은 방식으로 오른쪽 배열의 최소값 -71을 제일 마지막으로 이동시켜 보았다.

두 값을 붙이기 위해서 가운데 값들을 제거해 나간 다음 -92,-33,-71 이 남게 되는데, 이때 -92 또는 -71을 제거하기 위해 반드시 최솟값을 한번 제거해야 한다. 따라서 -92와 -71 사이의 값들은 남길 수 없다.

그리고 -71을 오른쪽 배열의 중간으로 이동시켜 보았다.

그리고 큰 값 제를 통해 -33, -72, -61을 -92와 짝을 지어 큰 값 제거로 제거하였다.

그 다음 남은 -92,-68 중에 작은 값 제거를 통해 -92를 날려주면 -68이 남는다.

하지만 -61을 남기기 위해서는 위 그림과 같이 -92,-61,-68까지 남길 수 는 있지만, 작은 값 제거가 반드시 한번은 실행되야 하므로, -61은 남길 수 없다.

 

이제 새로운 배열을 그려서 정리해보자.

1. 배열의 최소값을 기준으로 좌 / 우로 나눌 수 있다. 배열의 최소값은 언제나 남길 수 있다.

2. 배열의 최소값을 기준으로 좌/우로 나뉜 배열에서 다시 각 배열의 최소값을 찾는다.

3. 각 배열의 최소값과 기준값 사이의 값들은 남길 수 없다. 그 이유는 사이값을 남기기 위해서는 최소 2번의 작은 값 제거가 필요하기 때문이다.

4. 남겨진 배열에서 다시 최소값을 찾는다. 같은 이유로 최소값과 기준값 사이의 값은 남길 수 없다.

5. 계속 반복하며 좌우로 최소값을 찾아 나간다.

굉장히 길었던 설명에 비해 코드는 단순하게 마무리 되었다.

먼저 배열의 최소값을 찾아 절반을 나누고, 다시 각 left, right 배열에서 최소값을 찾아 answer에 1씩 추가해주는 방법으로 코드를 작성하였다.

문제는 이번에도 시간 초과라는 점이다...

그렇게 시간초과에 중점을 두고 다시 머리를 써서 완성한 코드이다.

역시나 배열을 왼쪽, 오른쪽으로 나누는데, 그냥 탐색 방향에 따라 나누었다.

그리고 각 배열에 a의 첫 값과, 끝 값을 넣어 주었다.

위에서 발견한 규칙에 의하면 배열의 최소값을 기준으로 A/B로 나누었을때 각 A,B의 최소값 과 배열의 최소값 사이의 숫자는 남길 수 없음을 활용하였다.

위 예시를 기준으로 코드를 돌려보면, 먼저 양쪽의 끝 값은 무조건 남길 수 있다.

그 이유는 기준값을 기준으로 모두 큰 값 제거를 실행한 후, 작은 값 제거로 기준값을 제거하면 되기 때문이다.

그리고 코드를 돌고나면 위 와 같은 left, right 리스트가 남게된다. 즉 a[0], a[-1]을 제외하고 지속적으로 큰값 제거를 하게 됐을때의 결과와 동일하다.

이를 set()을 이용하여 중복값을 제거해주고, 두 집합의 길이를 더한 다음 중복된 기준값을 한번 빼주면 완성이다.

합집합을 이용하는 방법도 있겠지만, 연산 속도에서는 그냥 각 길이를 더하고 1을 빼는게 더 빠르다.