[알고리즘]완주하지 못한 선수(프로그래머스 문제) python 풀이(정렬, 해시)

코딩테스트 처음 준비하는 사람을 위한 풀이방법

 

프로그래머스 해시(Hash)문제

https://programmers.co.kr/learn/courses/30/lessons/42576

 

먼저 문제를 보고 어떻게 푸는게 좋을지 사람에게 설명할수 있어야 코딩이 가능하다.

 

바로 풀이방법을 생각 하는게 어렵겠지만 쫌만 생각하면 한사람 씩 비교하는 방법 즉 2중포문을 사용하여 해결하는 방법은 생각할것이다. 풀이 방법이 생각났다면 바로 코딩해보자

 

2중포문으로 풀었더니 효율성에서 전부 실패 하였다. 이는 제한사항에 걸리기 때문이다. 2중포문은 시간복잡도 N^2 이다. 제한사항에 참여한 선수는 1명 이상 10만명 이하인데 10만을 N에 대입하면 100억이 된다. 100억이면 무조건 시간 초과로 테스트에 통과하지 못한다고 보면 된다. 마지노선을 1억이라 생각해야 한다.

 

2중포문 대신 다른 풀이 방법을 생각해보자

 

 

sort를 이용하여 풀었다. sort는 시간복잡도로 nlogn이다. 그리고 for문 하나가 있는 for문은 시간 복잡도 n

그래서 빅O로 봤을때 총 시간 복잡도는 nlogn이 된다.

n에 10만을 대입해보면 50만이다. 충분히 시간효율성에서 통과 할 수 있는 값이다.

 

 

위 방법으로 테스트를 통과했지만 이 문제가 해시 문제인걸 봤을때 해시로 어떻게 풀지 생각해 봐야 한다.

동명이인을 생각해야 한다고 했을때 참가자 이름을 key 명수를 value를 놓고 문제 풀이를 하였다.

코드에 for문이 여러번 있는데 여러번 있어도 빅오는 N이다. N에 10만을 대입하면 10만이다. 정렬을 해서 문제를 푸는 것보다 시간효율성이 좋다.

 

이처럼 2중포문말고 병렬식으로 for문을 놓고 푸는 것은 매우 바람직하다. 

해시를 사용한다는 것은 메모리를 사용한다는 것이다. 메모리와 시간은 상관관계다. 한쪽이 커지면 한쪽이 작아진다.

그래서 어느정도 메모리를 사용하여 시간을 줄이는 것이 효율적이다.