[프로그래머스] 풍선 터트리기 Lv.3

코딩테스트 연습 - 풍선 터트리기

알고리즘 공부를 본격적으로 시작한지 3개월이 되어가는 오늘, 실력이 점차 늘어간다는 느낌을 받는다.

월간 코드 챌린지에 도전하면서 세번째 문제였던 풍선 터트리기 문제에서 끝까지 66.7점을 받고 결국 2.6솔을 하고 끝났었다. 해당 문제가 프로그래머스에 업데이트 된 1일 후 오늘 다시 도전하였고, 효율성을 올려서 결국 100점을 받았다. 

 

첫번째 시도

 

처음에는 임의의 위치를 기준으로 왼쪽 그룹과 오른쪽 그룹으로 나눈 후, 각각의 그룹에 있는 원소들과 기준 위치 값을 비교하여 만약 기준 위치 값 보다 작은 값이 그룹에 있을 때, count를 늘리는 식으로 코드를 짰었다. 이렇게 하게 되면 배열의 길이가 100만이고 배열의 원소가 오름차순으로 나열된 데이터가 주어질 때 최약의 경우에 100만X100만 = 1조 의 시간복잡도가 나오게 된다. 

 

두번째 시도

 

왼쪽그룹의 시간복잡도를 줄이는 법을 알아냈었다. 주어진 배열의 가장 앞에 있는 원소 값을 변수 min 에 대입한다. 이후 for 문을 돌아가며 min 값을 업데이트 한다. 따라서 불필요한 비교 연산을 줄일 수 있게 되었고 점수는 66.7점이 나왔다. 하지만, 오른쪽그룹의 시간복잡도를 줄이지 못했다.

 

세번째 시도

 

오른쪽 그룹의 시간복잡도를 줄이기 시작해 보았다. setRightMin 함수를 따로 세팅해놓고, 현재 위치의 값과 rightMin 변수의 값이 같은 순간 이 함수를 호출하여 rightMin 을 오른쪽 그룹의 최솟값으로 세팅하는 방식이다. 하지만, 점수는 그대로 66.7점이 나왔다. 이유는 최악의 상황 때문인데, 주어지는 배열의 길이가 2만 이상이고 이 배열의 값이 오름차순으로 주어진다면 시간복잡도는 (2만 + 19999 + 19998 + ... + 1) 이므로 1억 이상의 시간복잡도가 나온다. 즉, 배열의 길이 2만 ~ 100만 사이의 오름차순 정렬된 데이터에 대해서는 무조건 시간초과가 뜰 수 밖에 없는 것이다. 최악의 상황은 배열의 길이 100만에 오름차순 정렬된 데이터 일때 인데, 이때는 O(10^12) ~ 5000억 정도의 시간복잡도를 가진다. 

 

네번째 시도

 

 동적계획법의 아이디어를 차용하여, 오른쪽 그룹의 값들을 임의의 테이블에 넣어놓고 오름차순으로 정렬해놓는 방법을 고안하였다. 따라서 매 순간마다 오른쪽 그룹의 최솟값을 구할 필요없이, 테이블의 가장 앞에 있는 값을 가져오면 되게 하였다. 최악의 시간복잡도 100만이 1로 줄어들게 하는 효과를 가져왔다. 하지만, 이 과정에서 처음에 list 의 remove() 메소드와 list 의 indexOf() 메소드를 사용하면 결국 모든 원소를  다 탐색하여 해당 값을 가지는 원소의 index 를 return 하는 방식이여서 의미가 없어짐을 알았다. 그래서 indexOf() 메소드 대신 해시맵 을 사용하여 해결을 시도하였다. 해시맵의 경우 해시를 사용하여 해당 key 에 바로 접근하여 value 를 얻어낼 수 있기에 사용하였다. 이때 key 값으로 배열의 원소값을 넣어놓고 value 에는 해당 원소값이 앞에서 이미 나온 것인지를 표시하는 Boolean 형태로 선언하였다. 그리고 나서 효율성이 개선되었고 문제를 맞을 수 있었다. 

 

코드

 

 

회고

 

3개월동안 250문제 가까이 풀었고, 실력이 예전에 비해 많이 늘었다는 느낌이 든다. 앞으로 더욱 알고리즘 공부에 전념하여 취업에 성공할 수 있기를