자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(Array_보이는 학생)

https://cote.inflearn.com/contest/10/problem/02-02

OnlineJudge

(위의 링크는 인프런 로그인 후, 해당 강의를 사지 않으면 접속이 되지 않습니다)

 

2. 보이는 학생

예시 입력 1 

8
130 135 148 140 145 150 150 153

예시 출력 1

5

 

 

내가 푼 풀이(Time: 741ms Memory: 35MB)

첫 번째 학생은 무조건 보이니까, 최종값과 최대값 변수는 초기화 세팅을해준다. 

또한 for문으로 반복문 돌릴때도 1부터 돌린다.

import java.util.Scanner;

public class Main {

    public int solution(int num, int[] array) {
        int ans = 1;
        // 첫 번째 학생은 무조건 볼 수 있으니까 1부터 순회
        int max = array[0];
        for (int i = 1; i < num ; i++) {
            if(array[i] > max) {
                max = array[i];
                ans++;
            }
        }
        return ans;
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = sc.nextInt();
        }
        System.out.println(T.solution(n,array));
    }
}

 

 

강의 풀이(Time: 698ms Memory: 35MB )

해당 문제를 2중 포문을 사용해서 150이 앞에 있는 숫자들 보다 큰지 이렇게 비교하면 안된다.

N이 10만이라서 O(n^2)이라서 실패하게 된다. 1000ms이다

 

첫 번째 학생은 무조건 보이니까 세팅해주고, 최대값 기록하는 방식으로 풀면 된다.

import java.util.Scanner;

public class Answer {
    public int solution(int num, int[] array) {
        int answer = 1, max = array[0];
        for (int i = 1; i < num; i++) {
            if (array[i]>max) {
                answer++;
                max=array[i];
            }
        }
        return answer;
    }
    public static void main(String[] args) {
        Answer T = new Answer();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = sc.nextInt();
        }
        System.out.println(T.solution(n,array));
    }
}