프로그래머스 - 등산코스 정하기(Python)

문제보기

https://school.programmers.co.kr/learn/courses/30/lessons/118669

프로그래머스

 

 

 

---

풀이 및 코드

 

처음에는 dfs, bfs로 풀려고 했다가 삽질을 좀 했다. 풀리긴 하겠지만 코드가 지저분해서 구현하는 데 오랜 시간이 걸렸고 시간초과로 인해 깔끔하게 다른 방법을 고민하던 중 다익스트라로 접근했다. 연결된 노드들 중에서 가장 작은 노드 부터 찾는 방식으로 구현했다. 하지만 파이썬이라 그런지 다익스트라로 구현해도 시간초과가 났고 다른 분들 코드와 비교해 가면서 몇가지 이유를 찾았다.

 

 - 시간 초과가 났던 이유

1. defaultdict : 이런 라이브러리가 있는 건 알고 있었지만 익숙하지 않아 dict의 get 함수를 많이 썼다. get('a', []) 이런 식으로 자주 사용했는데 개수가 많아지니 get을 이용한 방식으로는 시간 초과가 발생함을 알 수 있었다.

2. if 'a' not in list :  파이썬 함수 중에서 가장 애용했던 것 중 하나가 list에서 not in 을 통해 조건문을 만드는 방식이었다. 하지만 사용 빈도가 많아진다면 list에서 not in 을 사용하는 것 보다는 set에서 in 조건을 사용하는 것이 시간 개선에 도움이 되었다.

 

필자는 이 두가지를 고치니 시간 개선이 되어 통과 되었다.. 알고리즘이 맞아도 시간초과가 나는 걸 보면 파이썬의 단점이 확실히 보인다.