[python3] 17608 막대기 / insert와 append의 차이

https://www.acmicpc.net/problem/17608

17608번: 막대기

[ 맨 처음 생각한 풀이 ]

 

오른쪽에서 봤을 때의 막대기 개수를 구하는 것이라면, 막대기 높이를 입력 받을 때 애초에 뒤집어진 채로 입력받는게 직관적일 것이라 생각했다. 다른 방법으로는 순서대로 입력 받은 뒤 list를 reverse()해서 뒤집는 방법, for문을 -1씩 읽는 방법 등까지 생각을 해 놓았다.

 

* 간과했던 것 : insert(), append()의 시간 복잡도를 간과하고 있었다. insert()는 원하는 자리에 삽입할 수 있다는 장점이 있으나, 시간 복잡도는 O(N), append()의 시간복잡도는 O(1)로,  시간 초과 조건이 존재하고, 나머지 코드가 동일하다면 append()를 사용하는 것이 효율적이라는 것을 간과했다. 바보~

 

시간 초과 풀이

 

정답 풀이