[BOJ-JS] 1946번 - 신입 사원

1946번: 신입 사원 (acmicpc.net)

1946번: 신입 사원

처음에 LIS 문제인줄 알았는데 다시 보니 스탈린 정렬 문제였다. 두 성적 중 하나로 먼저 내림차순 정렬한 다음, 남은 성적으로 스탈린 정렬 해버리면 끝난다. 즉, O(n)짜리 그리디 문제.

a=(0+require('fs').readFileSync(0)).split`
`
p=1
while(a[0]--){
  b=+a[p]
  q=r=0
  a.slice(p+1,p+b+1).map(j=>j.split` `.map(e=>b-e)).sort((x,y)=>y[0]-x[0]).map(e=>{if(r<=e[1]){q++;r=e[1]}})
  console.log(q)
  p+=b+1
}