[알고리즘] 풍선 터트리기 (월간 코드 챌린지 시즌1 - 9월)
코딩테스트 연습 - 풍선 터트리기 [-16,27,65,-2,58,-92,-71,-68,-61,-33] 6 programmers.co.kr 월간 코드 챌린지 9월에 나온 레벨3 문제다. 9월 10월 둘 다 풀면서 느낀건 브루트 포스 문제보단 아이디어로 시간복잡도를 최소화 해가면서 푸는 방식을 원하는 것 같다. 이 문제 또한 N이 최대 1백만이기에 O(N ^ 2)으론 풀 수가 없다. Solution 먼저 파악해야할 것은 어떤 특정값이 최후까지 살아남는지 알아볼 때, 양쪽에 있는 수들은 서로 만날 수가 없다. 그렇기에 특정값을 기준으로 왼쪽 오른쪽으로 나누어서 살펴봐야 한다. 그리고 양쪽에서 최후까지 살아남을 수 있는 수는 각각 2가지가 되는데 '최소값, 최소값보다 한단계 더 큰 값'이 될 수 있다. 최소값은..
2020. 10. 9.