안녕하세요, Will 입니다. 오늘은 프로그래머스 연습문제 중 '달리기 경주' 문제 풀이를 가지고 왔습니다. 난도가 높은 문제로 보이지 않았는데 막상 풀어보니 시간초과가 발생하여 애를 좀 먹었습니다. 시간복잡도와 Big-O 표기법과도 연관이 있는 문제이며, 개념을 정리해두기 위해 블로그에 남기게 되었습니다. 결론부터 말씀드리면 검색 시에 Dictionary를 활용하면 for문, list의 index() 함수를 이용할 때보다 시간복잡도를 낮출 수 있으며, 검색 시간을 대폭 감소 시킬 수 있습니다. 문제 얀에서는 매년 달리기 경주가 열립니다. 해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부릅니다. 예를 들어 1등부터 3등까지 "mumu", "soe", "poe" 선수들이 순서대..
