[Algorithm] 보이는 학생 -> 입력 및 복잡도 생각하고 풀기

설명

선생님이 N명의 학생을 일렬로 세웠습니다. 일렬로 서 있는 학생의 키가 앞에서부터 순서대로 주어질 때, 맨 앞에 서 있는

선생님이 볼 수 있는 학생의 수를 구하는 프로그램을 작성하세요. (앞에 서 있는 사람들보다 크면 보이고, 작거나 같으면 보이지 않습니다.)

입력 

첫 줄에 정수 N(5<=N<=100,000)이 입력된다. 그 다음줄에 N명의 학생의 키가 앞에서부터 순서대로 주어진다.

출력 

선생님이 볼 수 있는 최대학생수를 출력한다.

 

 

이번 문제는 입력을 잘 읽어야한다..

처음에 2중 for문으로 풀면 되겠구나 싶어서 풀어보려다가 발견한게, 100,000개의 케이스가 입력되었을 때, 2중 for문으로 풀게되면 O(n^2) 의 복잡도를 띄게 되고 1초안에 실행이 될 수 없는 것을 알게 되었다.

즉 , 이 문제는 최대 값(학생의 키) 를 갱신해가며 count를 증가시키는 방법으로 해결하면 됐다.

import java.util.*;

public class Array2 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] studentHeight = new int[n];

        for(int i = 0 ; i < studentHeight.length; i++){
            studentHeight[i] = sc.nextInt();
        }

        System.out.println(solution(studentHeight));
    }

    private static int solution(int[] input) {
        int count = 1; // 맨 앞은 무조건 보임
        int tallest = input[0]; // 최장신을 제일 앞 학생으로 초기화

        // 2중 for문 사용시 시간 초과
        for (int i = 1; i < input.length; i++) {
            if (input[i] > tallest) {
                count++;
                tallest = input[i];
            }
        }

        return count;
    }
}