정렬 알고리즘(백준 10989번)

 

이 문제는 얼핏 봐서는 굉장히 쉬워 보일 수 있으나, 시간 제한과 메모리 제한을 생각해야 한다. 

 

Python이 1초에 2천만번 정도의 연산만 처리할 수 있다고 가정하고 문제를 접해야함

참고

N의 범위가 500인 경우: 시간 복잡도가 O(N³)인 알고리즘을 설계하면 문제를 풀 수 있음  N의 범위가 2,000인 경우: 시간 복잡도가 O(N²)인 알고리즘을 설계하면 문제를 풀 수 있음  N의 범위가 100,000인 경우: 시간 복잡도가 O(NlogN)인 알고리즘을 설계하면 문제를 풀 수 있음   N의 범위가 10,000,000인 경우: 시간 복잡도가 O(N)인 알고리즘을 설계하면 문제를 풀 수 있음

 

따라서 O(N)인 알고리즘을 설계해야 하는데 O(N)인 알고리즘은?

계수 정렬!

 

계수 정렬을 이용하여 문제를 풀어야 한다는 것을 알 수 있다,

 

계수 정렬을 이용하여 값의 범위가 1~10000까지이므로 이 값의 범위의 인덱스에 해당하는 곳에 +1씩 해준다

또한 해당 인덱스의 값만큼 반복을 수행하여 중복값 처리까지 해주면 결과가 나온다