임의의 요소의 값보다 요소의 값이 다 작은 경우가 한번이라도 있다면?

프로그래머스 인사고과 문제의 포인트이다

 

완호네 회사는 연말마다 1년 간의 인사고과에 따라 인센티브를 지급합니다. 각 사원마다 근무 태도 점수와 동료 평가 점수가 기록되어 있는데 만약 어떤 사원이 다른 임의의 사원보다 두 점수가 모두 낮은 경우가 한 번이라도 있다면 그 사원은 인센티브를 받지 못합니다.

 

[[2,2],[1,4],[3,2],[3,2],[2,1]]

이런 배열의 경우 4번째 요소인 [2,1]은 2번째,3번째 요소보다 모든 요소의 값이 작기 때문에 걸러진다.

 

이제 최대 100000개의 요소가 들어있는 배열에서 요소들을 걸러야 하는데 10만개라서 N^2으로는 풀이를 할 수 없다. 하지만 정렬을 이용하면 N으로 풀이가 가능하다.

 

첫번째 요소를 기준으로 내림차순 정렬, 두번째 값 기준으로 오름차순 정렬을 한다. 그럼 첫번째 요소는 더이상 생각해줄 필요가 없다. 두번째 요소를 앞에서부터 돌며 두번째 요소의 최대값을 찾고 최대값보다 값이 작다면 걸러준다.

 

10 10 10 9 9 9 8 8 7

1   2   4   1 2 5 3 4 5

순차적으로 최대값이 1 -> 2 -> 4 -> 5 로 변하며 이보다 작은 값은 걸러지는 것이다.

 

scores.sort(key=lambda x:(-x[0],x[1]))

요소 정렬