[C++]분노 유발자

내 답

#include <iostream>
#include <stdio.h>

int main() {
    int N , i, j, num, cnt2 = 0,cnt = 0;
    int stu[100];
    //max를 이용하면 한번만 돌아도 구할 수 있는데
    //이건 2중 for문을 써야할 것 같음
    
    scanf("%d",&N);
    
    for(i = 0; i < N; i++){
        scanf("%d",&stu[i]);
    }
    
    for(i = 0; i < N-1; i++){
        num = (N-1) - i;
        
        for(j = i+1; j < N; j++){
            if(stu[i] > stu[j]) cnt++;
        }
 
        if(cnt == num) cnt2++;
        
        cnt = 0;
    }
    
    printf("%d",cnt2);
    
    return 0;
}

• 배열에 값들을 저장해놓고
• i로 기준을 잡고 그 다음 인덱스를 체크하면서 기준이 다음 인덱스보다 크면 카운팅한다.
• 카운팅한 수와 뒷자리에 앉은 학생들의 수가 일치하면 모든 학생들을 가리고 있는 것이므로 cnt2를 증가시킨다.
• NlogN정도의 시간이 걸릴 것이라고 예상한다.
• 일반적으로 인덱스 내부에서 가장 큰 인덱스를 찾는 등의 비교를 할때에는 2중 for문을 사용해야만 한다고 생각했던게 안일했다.

더 효율적인 답

int main() {
    int n, i, cnt = 0, h[101], max;
    scanf("%d",&n);
    
    for(i = 1; i <= n; i++){
        scanf("%d",  &h[i]);
    }
    
    max = h[n]; // 배열에서 max활용하기
    //뒤에서부터 비교할 것이므로 맨 뒤의 값을 max로 잡는다.
    
    for(i = n-1; i >= 1; i--){ //뒤에서부터 체크한다.
        if(h[i] > max){ //max보다 그 다음 인덱스가 크면
            max = h[i];
            cnt++; //카운트 하나 올린다.
        }
    }
    
    printf("%d\n",cnt);
    
    return 0;
}

• 배열에서 max활용하는 방법이다.
• N만큼의 시간에 효율적으로 해결되었다.
• 뒤에서부터 비교할 것이라고는 생각을 못했다.
• 배열에서 max활용하는 방법은 다른 문제에서도 매우 유용할 것 같다.