보이는 학생

문제풀이

 선생님이 N(1<=N<=1000)명의 학생을 일렬로 세웠다. 일렬로 서 있는 학생의 키가 앞에서부터 순서대로 주어질 때, 맨 앞에 서 있는 선생님이 볼 수 있는 학생의 수를 구하고자 한다.

(앞에 서 있는 사람들보다 크면 보이고, 작거나 같으면 보이지 않는다)

 

이중 for문을 돌려 자신의 앞에 있는 학생들 중 자신보다 큰 키를 지닌 학생들이 없을 경우에만 해당 학생을 카운트해주는 방식을 생각해 볼 수 있다. 하지만 이중 for문 O(n2)은 시간 복잡도 상 한번의 for문 O(n)보다 2배 더 소요되기 때문에 max 변수를 하나 더 선언해 주어 풀이하였다.

 

max와 같은 경우는 가능한 최솟값을 지녀야 되기 때문에 Number.MIN_SAFE_INTEGER로 나온 값을 초기화 해주었고, for문 내에서 만약 앞에 사람보다 크고 지금까지 순회한 학생들의 키 중 가장 큰 키를 지닌 학생보다 더 클 경우에만 해당 값을 push해주고 max값을 재할당해주었다.

> (오답)  조건식 내에 arr[i] > arr[i - 1]은 불필요하다. 바로 앞 사람보다 클 경우를 검사하지 않더라도 max(자신의 앞에 있는 학생들 중 가장 큰 키를 지닌 학생)보다 크기만 한다면 맨 앞에 선생님이 볼 수 있다.