🧮 [프로그래머스] 달리기 경주

문제

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

프로그래머스

 

문제이해 & 풀이

 

문제를 이해하는것 자체는 굉장히 쉽다. 가끔 이런 문제는 넌센스 같은 느낌으로 푼적이 있다.

설명

현재 달리고 있는 선수들(players)중에 해설진들이 선수를 호명(callings)하면 그 선수는 자신 바로 앞에 있는 선수를 제쳤다! 라는 뜻이다.

 

이 문제의 큰 산은 문제에 대한 이해가 아니라 시간복잡도이다. 문제의 조건 중 이러한 조건이 있다.

이 조건은 2중 for문의 시간복잡도(O(n2))에서 문제가 생긴다. callings의 제곱이 1억을 넘게 되면 시간초과가 발생할 수 있다는 것이다. 

 

실패한 나의 코드

 

그래서 2번째안 해시함수를 사용하는것이다. 해시의 시간 복잡도는 O(n)으로써 전혀 문제가 되지 않는다는 것이다. 

HashMap 을 이용해서 문제를 푸는것이 해답이다.

 

소스 코드