문제
: N명의 아이들 키가 순서대로 입력되었을 때 , 맨 앞에 위치한 선생님 입장에서 보이는 아이들의 숫자는 몇명일까?
(이때 아이1,2,3,4,5,6,7,8이 서 있을 때, 아이 4 입장에서는 아이1,2,3보다 모두 키가 커야 아이 4가 선생님에게 보이게 된다. 만약 아이1,2,3들의 키와 같거나 작다면 아이4는 선생님에게 보이지 않게 된다.)
이 문제의 요구사항은 곧 "입력된 배열의 각 element에 대해서, 자신보다 앞선 모든 element들 보다 더 큰 값을 갖는 element"의 개수를 count하는 것 이라고 할 수 있다.
이에 대한 해결 로직으로는 , 각 element 기준으로 앞선 모든 element들과 비교하는것이 아니라 , 그중에서 가장 큰 최댓값 하고만 비교 하는 방법을 생각할 수 있다.
[좀더 구체적으로 설명하자면]
130 135 148 140 145 150 150 153 이 입력되었을 때
130 부터 순차탐색을 하면서 , 탐색 중간 중간의 max 값을 저장하면 된다.
그러면 130 - 135 - 148 - 140 까지 탐색했을 때의 max는 148이 되고,
이후 탐색할 145는 max인 148보다 작으니 보이지 않을것이라고 바로 판단할 수 있다. (순차탐색을 위한 loop을 한번만 돌면서도 count 가능!)
이러한 해결로직으로 구현한 코드가 바로 아래의 코드이다.
이때 나의 경우는 가장 앞에 위치한 아이는 반드시 보이면서 중간 최댓값이 될 수 있으므로, 이를 위해 탐색 전 max를 -1로 초기화 하였다.
(키는 절대 음수가 될 수 없으니깐, 어떤 키가 와도 음수보단 큼)
import java.util.Scanner;
public class Main {
public static int solution(int[] arr, int N){
int cnt = 0;
int max = -1;;
for (int i : arr) {
if(i > max){
cnt++;
max = i;
}
}
return cnt;
}
public static void main(String[] args) {
//0. Scanner 준비
Scanner sc = new Scanner(System.in);
//1. N과 N개의 키가 순서대로 입력
int N = sc.nextInt();
int[] arr = new int[N];
for(int i=0; i<N; i++){
arr[i] = sc.nextInt();
}
//2. arr와 N을 인자로 넘기면서 solution()을 호출하여 , 결과를 반환
int result = solution(arr, N);
//3. 반환받은 결과를 출력
System.out.println(result);
}
}