군대에서_코딩하기_알고리즘_10

또 오랜만이다.. 육군본부에서 진행하는 UCC 공모전때문에, 며칠동안 공백이있었다..앞으로도 며칠 더 있겠지만, 일단 오늘은 공부를 했다..
오늘 문제는 1차원 배열을 이용해서 풀어야되는 문제였다. 자연수 N이 주어지고, N만큼의 숫자들이 주어지는데, 이 숫자들이 사람의 '키'라고 가정했을 때, 뒷사람 모두의 시야를 가리는만큼의 키를 소유한 사람이 몇명이나 있는지 알아내는 것이다.
그냥 무식하게 for문 2개를 이용해서 숫자들을 일일히 다 비교하는 방법도 있지만, 뭔가 좀 더 간결하고 똑똑한 방법을 이용하고 싶었다.
일단 코드는 다음과 같다.

#include<iostream>

using namespace std;

int main(){
    
    int N, cnt=0, i, j, max, check;
    int list[100];
    cin>>N;
    
    for(i=0; i<N; i++){
        cin>>list[i];
    }
    
    max = list[0];
    
    for(i=1; i<N; i++){
        for(j=i; j<N; j++){
            if(max<=list[j]){
                i = j;   //4로 바뀜 i가
                max = list[j]; //max가 76으로 바뀜
            }
            
        }
        cnt++;
        max = list[i+1];
    }
    
    cout<<cnt-1;
}

단순히 for문을 두번 이용해서 N^2 의 시간복잡도를 가진것이 아니라, 쓸데없는 비교를 하지 않기 위해, max값을 새로 뽑아내면, 그 이전의 것들은 다 버리는 방식을 택했다. 이 방식이면 아마 N이 훨씬 커져도 런타임에 무리가 없을것같다.