[Swift] 프로그래머스 - 풍선 터트리기

문제

https://programmers.co.kr/learn/courses/30/lessons/68646

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

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

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

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

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

주의할점

• 인접한 두 풍선 중에서 번호가 더 작은 풍선을 터트리는 행위는 최대 1번만 할 수 있음. -> 작은풍선이 살아남을 수 있는데, 딱한번 큰풍선이 살아남을 수 있음
• 인접한 두 풍선임..

접근 방법

인접한 두 풍선이고.. 작은 숫자가 살아남아야 마지막 타겟숫자가 큰숫자라도 한번이라도 더 살 수 있기 때문에, 결과적으로

[-16,27,65,-2,58,-92,-71,-68,-61,-33]

이런 숫자 중 -2가 살아남는지 확인하려면

-2 기준 좌측인 [-16,27,65] 중 가장 작은 숫자인 -16이 살고

-2 기준 우측인 [58,-92,-71,-68,-61,-33] 중 가장 작은 숫자인 -92가 살아남는다.

즉 [-16,-2,-92] 요렇게만 보면 되는데,

타겟넘버인 -2가 둘 중 하나라도 작은 값이 있다면 2번의 러시안룰렛..? 중 1번은 목숨을 살 수가 있기 때문에 결과적으로 true, 살아남는 풍선이 된다는걸 알 수 있다.

요런식으로 for문을 돌면서 하나하나 살아남는여부를 체크해주면 되는데, 0,마지막 인덱스값은 좌측이나 우측 array가 없으므로 결국 마지막 array에서 갯수가 2개인 array로 남게 된다. 즉 1번의 러시안룰렛에서 목숨이 1개가 더 있기 때문에 무조건 true, 그러므로 for문에서 제외하고 애초에 +2를 해주자.

이 방법을 알아내고 와! 이게 정답이다 최고다 생각했는데.. 시간초과가 났다..

그리고 질문하기 글 목록을 봤는데, 대부분 요렇게 생각했는데 시간초과가 났다고 한다. 그리고 최소화 하는 메소드 min() 표준라이브러리를 사용하는 것 보다 더 빠른걸 사용해야 통과를 할 수 있다고..

 

해결

매번 좌우 모든 array의 최솟값을 찾는건 비효율적이다. 이부분에서 서치하는 과정을 줄임으로써 문제를 해결했다. ㅇ_ㅇ

서치는 좌 -> 우 측으로 서치를 할 것이기 때문에, 타겟넘버 좌측의 최솟값은 비교적 구하기 쉽다. 이전값보다 더 작다면 최솟값을 갱신해주면 된다. 굳이 idx 0부터 서치할 필요가 없다는 말씀. 이는 for문을 1 부터 n-1 까지 서치하는 순서로 진행했기 때문에 가능하다.

문제는 타겟넘버 우측라인의 최솟값을 구해주는 방법이다. 만약 더 작은 값이 있다면 최솟값으로 바꿔주는 작업을 해줘야 했기 때문에, 이전 작업물을 굳이 중복적으로 서치할 필요가 없다는걸 알게 되었다. 즉 dp로 해결하면 된다는 생각을 했다.

처음 시작하는 부분에서 우측 최솟값을 dp로 만들어줬기 때문에 중복 서치하는 횟수가 줄어들어서 통과하게 되었다.

코드

1.시간초과코드 ㅠ

2.수정 후 통과한 코드