10816 백준 숫자카드2

문제는 다음과 같이 10개의 수가 주어지고 8개 수 중 몇개가 들어있는지 나열하는 것이다.

 

나는 counting sort를 이용해서 풀었는데 시간이 오래 걸려서 다른 방법을 찾아보았다.

중복되는 수 때문에 이진 탐색을 이용할 수 없다 생각하여 counting sort를 활용하였는데

lower_bound, upper_bound를 이용해서 쉽게 해결할 수 있더라..

 

counting sort를 이용한 문제 풀이.

소스 코드를 직접 구현하면 이런 느낌이다.

 

이 것을 내장함수로 표현하면 다음과 같다.

훨씬 더 소스코드가 간결해졌지만 실행 시간은 counting sort와 비슷한 결과를 가져다 주었다.

 

 

메모리 차이는 많이 나더라..