[배열] 보이는 학생

보이는 학생

선생님이 N명의 학생을 일렬로 세웠습니다. 일렬로 서 있는 학생의 키가 앞에서부터 순서대로 주어질 때, 맨 앞에 서 있는 선생님이 볼 수 있는 학생의 수를 구하는 프로그램을 작성하세요.
(어떤 학생이 자기 앞에 서 있는 학생들보다 크면 그 학생은 보이고, 작거나 같으면 보이지 않습니다.)

---

제한사항

• N은 5 <= N <= 100,000

---

입출력 예

입력

130 135 148 140 145 150 150 153

출력

5

---

이중for문으로 문제를 해결할 경우, N의 최대값은 100,000이므로 실행시간이 O(n2)이 되어 1,000ms를 초과하게 된다.

이중for문 사용하지 않고, i 보다 큰 max값에 담긴 값을 변경하며 문제 해결.

import java.util.*;
class Main {
	public int solution (int n, int[] arr) {
   	int answer=1, max=arr[0];
       for (int i=1; i < n; i++) {
       	if (arr[i] > max) {
           	answer++;
               max = arr[i];
           }
       }

       return answer;
   }
}

public static void main(String[] args) {
	Main T = new Main();
   Scanner kb = new Scanner(System.in);
   int n=kn.nextInt();
   int[] arr = new int[n];
   for (int i=0; i<n; i++) {
   	arr[i] = kb.nextInt();
   }
   System.out.println(T.solution(n, arr));
}