백준 C++ 25305번 커트라인 ( sort, nth_element )

 

요즘 읽고 있는 책에서

일의 우선순위를 정하라고 알려주었다.

 

반드시 해야 함

해야 함

하면 좋음

 

이렇게 3단계로 나누어서 하면 좋다고 했다.

내 다이어리에 그렇게 쓰려니 뭔가? 뭔가??? 좀 잘 안된다..ㅋㅋ

 

흠.....

그렇게 내 다이어리에 어떻게 정리하지? 를 두 시간이나 고민했다.

이왕 쓰는 거 예쁘게 쓰고 싶은 내 마음이다.

---

 

 

내 계획은 이랬다.

 vector로 받고 내림차순으로 정리한 다음에

k값을 내라고 하면 될 거 같았다. 뭐 정확히 k-1이겠지만

 

흠..

 

 

그렇다. 이 사람 sort를 까먹은 모양새다.

 

제씨를 찾으러 갔다.

 

똑똑한 녀석 나에게 바로 sort의 함수 사용법을 모르냐고 물었다.

ㅋㅋㅋㅋㅋㅋ

 

sort

정렬

기본적인 사용법은 시작지점과 끝 지점을 인자로 주는 것

sort(v.begin(), v.end());

 

그럼 반대는?

sort(v.end(), v.begin());

반대로 해주면 될 거 같지만? 그렇지 않다..

 

그냥 원래식에다가

greater<int>()를 달아주어야 한다.

그래서

sort(v.begin(), v.end(), greater<int>());

 

이렇게 해주어야 한다고 한다.

잊지 마시오!! <int> 하고 괄호 두 개가 꼭 필요하다..ㅎㅋ

 

그리고 굳이 뭐 내림차순으로 꼭 할 필요도 없다.

오름차순으로 하고 출력을 전체에서 k번째로 빼주면 ( 사실은 더 )  간단하다.

 

 

 

나의 제씨..

더 좋은 방법이 있다며 또 나의 글을 늘리게 해 주는군..

 

사실 이 sort의 경우 모든 글자를 확인하고 정렬하기 때문에

시간복잡도가 O(n log n)이라고 한다.

하지만 O(n)인 방법도 있다는데

그의 이름

 

nth_element

전체 정렬을 하지 않고, 기준점을 잡아 특정 요소만 제 위치에 가져다주는 함수이다.

이 친구는몇 번째 자리에 올 친구만 찾고 나머지는 대충 그거보다 큰지 작은지만 분류해 준다.

 

sort랑 사용법이 비슷하다

기본형은

(시작, 찾고자 하는 지점, 끝) 이여서

nth_element(v.begin(), v.begin()  + (k - 1), v.end());

이고

 

내림차순은 아까 그 보라친구 

 greater<int>()  를 써서

nth_element(v.begin(), v.begin()  + (k - 1), v.end(), greater<int>());

해주면 된다.

 

 

이 친구의 원리가 궁금해져서 알아보았다.

 

1000명의 학생이라고 예시를 들어보자

딱 10등의 학생의 점수를 가지고 싶다.

그렇다면 먼저

아무나 뽑는다. 이 친구가 80점이라고 치면

80점보다 낮은애 들은 그냥 다 왼쪽으로 보낸다.

 

툭툭툭툭

흠.. 줄을 세워보니 80 이상이 100명이네?

 

그러면 다시 80보다 높은 점수를 기준으로 잡고

오른쪽 왼쪽 툭툭툭툭 해줘서

10등을 찾은 것이다!

900명은 굳이 79가 누군지 60이 누군지 정렬해 줄 필요 없으니 계산 외가 된다.

 

 이 기준점을 내부 알고리즘이 스스로 결정한다고 한다.

참 신기하다.

 

숫자가 커지면, 이 친구가 더 효율적이라고 한다.

 

알았다. 

nth_element 친구를 배웠다.